10600 - ACM Contest and Blackout

為了舉辦"國際ACM世界學校競賽"，市長決定為每所學校提供穩定可靠的電力，為了達成這個目標，其中某一所學校的電力系統必須與發電廠直接連接，且部份學校間的電力系統亦需互相連接。

用來評估一所學校的電力是否穩定的原則為：1. 若某學校的電力系統與發電廠直接相連，則該學校的電力是穩定的，2. 或某學校與另一所電力穩定的學校直接相連，則該學校的電力也是穩定的。給定學校間彼此連線的成本，市長必須決定兩種可能的連線路線使得成本最小。成本 的計算為學校間的連線成本總和。請你幫市長找出兩種最便宜的連線路徑。

Input

輸入的一開始有一個整數T(1 <= T <= 15)表示測試資料的組數，接下有來T組測試資料，每組資料的一開始有兩個以空白字元隔開的整數N, M，N(3 <= N <= 100)表示學校的總數，M表示學校間可能的連線數，接下來有M組連線，每組有三個整數Ai, Bi, Ci，Ci(1 <= Ci <= 300)表示Ai與Bi兩所學校的連線成本。學校的編號為1~N。

Output

每組測試資料輸出一列，每列有兩個以空白字元隔開的整數S1, S2，分別表示最低連線成本與次低連線成本，S1 <= S2。你可以假設S1, S2必存在。

Sample Input	Sample Output
2 5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66 9 14 1 2 4 1 8 8 2 8 11 3 2 8 8 9 7 8 7 1 7 9 6 9 3 2 3 4 7 3 6 4 7 6 2 4 6 14 4 5 9 5 6 10	110 121 37 37

原文出處