用來評估一所學校的電力是否穩定的原則為: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 |
沒有留言:
張貼留言