[USACO09JAN]安全出行Safe Travel

题目描述

Gremlins have infested the farm. These nasty, ugly fairy-like creatures thwart the cows as each one walks from the barn (conveniently located at pasture\_1) to the other fields, with cow\_i traveling to from pasture\_1 to pasture\_i. Each gremlin is personalized and knows the quickest path that cow\_i normally takes to pasture\_i. Gremlin\_i waits for cow\_i in the middle of the final cowpath of the quickest route to pasture\_i, hoping to harass cow\_i. Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from pasture\_1 (the barn) to pasture\_i. Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow\_i that avoid gremlin\_i who is located on the final cowpath of the quickest route from pasture\_1 to pasture\_i. As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a\_i (1 <= a\_i <= N) and b\_i (1 <= b\_i <= N) and requires t\_i (1 <= t\_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a\_i != b\_i). Best of all, the shortest path regularly taken by cow\_i from pasture\_1 to pasture\_i is unique in all the test data supplied to your program. By way of example, consider these pastures, cowpaths, and [times]: ```cpp 1--[2]--2-------+ | | | [2] [1] [3] | | | +-------3--[4]--4 ``` ``` TRAVEL BEST ROUTE BEST TIME LAST PATH p_1 to p_2 1->2 2 1->2 p_1 to p_3 1->3 2 1->3 p_1 to p_4 1->2->4 5 2->4 ``` When gremlins are present: ```cpp TRAVEL BEST ROUTE BEST TIME AVOID p_1 to p_2 1->3->2 3 1->2 p_1 to p_3 1->2->3 3 1->3 p_1 to p_4 1->3->4 6 2->4 ``` For 20% of the test data, N <= 200. For 50% of the test data, N <= 3000. TIME LIMIT: 3 Seconds MEMORY LIMIT: 64 MB 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的最短路经是唯一的.

输入输出格式

输入格式


\* Line 1: Two space-separated integers: N and M \* Lines 2..M+1: Three space-separated integers: a\_i, b\_i, and t\_i

输出格式


\* Lines 1..N-1: Line i contains the smallest time required to travel from pasture\_1 to pasture\_i+1 while avoiding the final cowpath of the shortest path from pasture\_1 to pasture\_i+1. If no such path exists from pasture\_1 to pasture\_i+1, output -1 alone on the line.

输入输出样例

输入样例 #1

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

输出样例 #1

3 
3 
6 

说明

感谢 karlven 提供翻译。