Gremlins have infested the farm. These nasty, ugly fairy-like creatures thwart the cows as each one walks from the barn (conveniently located at ) to the other fields, with traveling to from to . Each gremlin is personalized and knows the quickest path that normally takes to . waits for in the middle of the final cowpath of the quickest route to , hoping to harass .
Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from (the barn) to .
Compute the best time to traverse each of these new not-quite-quickest routes that enable each that avoid who is located on the final cowpath of the quickest route from to .
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 (1 <= <= N) and (1 <= <= N) and requires (1 <= <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (). Best of all, the shortest path regularly taken by from to is unique in all the test data supplied to your program.

By way of example, consider these pastures, cowpaths, and [times]:
      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:
   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.

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Three space-separated integers: , , and 

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

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

3
3
6