P2934 [USACO09JAN] Safe Travel G

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 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

\* 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.