Problem : 137 - 安全路徑

Problem Statistics

Solved Member: 5　　Submission: 52　　User Tried: 9

Statement:

有 n 個農場，由 1 編號到 n。農場之間以 m 條雙向的道路相連，每條道路有通過所需要花費的時間。

每隻牛會固定在農場 1 聚會，並在聚會完後回到自己的農場(編號 2 到 n)。由於這些牛很懶，他們會延著耗時最短的路徑走回自己的農場，並且這條最短的道路是唯一的。

*農場間的道路圖

某天，農場為了鼓勵這些牛多運動實施了一個政策，每頭牛回到農場時不允許經過回到自己農場最短路中的最後一條路。如住在農場 4 的牛，回到農場的最短路徑為 1-2-4，在這項新政策實施之後這隻牛不能經過 2-4 這條道路，而住在 2 的牛則不允許經過 1-2 這條路。

這些牛想知道在這項新政策實施之後，他們最少要花多少時間才能回到原本住的農場，於是他們想請優秀的你來幫忙。

Input:Output:

第 1 行有 2 個整數 n,m(n ≤ 100000; m ≤ 200000)，以空格分隔，代表農場個數以及道路的個數。
接下來的 m 行每行有 3 個整數 a,b,c，代表有一條道路連接農場 a 與農場 b，需花費時間 c，其中 1 ≤ c ≤ 1000。

請輸出 n-1 行，第 i 行請輸出住在農場 i+1 的牛在實施新政策之後回到自己農場最少需花費多少時間，若對於農場 i+1 不存在這樣的路徑請輸出-1。

Sample Input:Sample Output:

4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

3
3
6

Source:

USACO 2009 Jan. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1500ms	65536kb
1	1500ms	65536kb	10
2	1500ms	65536kb	10
3	1500ms	65536kb	10
4	1500ms	65536kb	10
5	1500ms	65536kb	10
6	1500ms	65536kb	10
7	1500ms	65536kb	10
8	1500ms	65536kb	10
9	1500ms	65536kb	10
10	1500ms	65536kb	10