Gremlins最近在農場上氾濫,它們經常會阻止牛們從農莊(牛棚_1)走到別的牛棚(牛_i的目的
地是牛棚_i).每一個gremlin只認識牛_i並且知道牛_i一般走到牛棚_i的最短路經.所以它
們在牛_i到牛棚_i之前的最後一條牛路上等牛_i. 當然,牛不願意遇到Gremlins,所以準備找
一條稍微不同的路經從牛棚_1走到牛棚_i.所以,請你為每一頭牛_i找出避免gremlin_i的最
短路經的長度.

和以往一樣, 農場上的M (2 <= M <= 200,000)條雙向牛路編號為1..M並且能讓所有牛到
達它們的目的地, N(3 <= N <= 100,000)個編號為1..N的牛棚.牛路i連接牛棚a_i
(1 <= a_i <= N)和b_i (1 <= b_i <= N)並且需要時間t_i (1 <= t_i <= 1,000)通過.
沒有兩條牛路連接同樣的牛棚,所有牛路滿足a_i!=b_i.在所有數據中,牛_i使用的牛棚_1到牛
棚_i的最短路經是唯一的.

以下是一個牛棚,牛路和時間的例子:

　　　１－－［２］－－２－－－－－－－＋
　　　∣　　　　　　　｜　　　　　　　｜
　　［２］　　　　　［１］　　　　　［３］
　　　｜　　　　　　　｜　　　　　　　｜
　　　＋－－－－－－－３－－［４］－－４

　　行程　　　　最佳路徑　　最佳時間　　最後牛路
　　p_1到p_2　　　1→2　　　　　2　　　　　1→2
　　p_1到p_3　　　1→3　　　　　2　　　　　1→3
　　p_1到p_4　　　1→2→4　　　  5　　　　　2→4

當gremlins進入農場後:

　　行程　　　　最佳路徑　 最佳時間　　　最後牛路
　　p_1到p_2　　　1→3→2　　　3　　　　　1→2
　　p_1到p_3　　　1→2→3　　　3　　　　　1→3
　　p_1到p_4　　　1→3→4　　　6　　　　　2→4