Avoiding Gremlins on the Farm

Gremlins have infested the farm! The cows normally traverse from the barn (pasture \(1\)) to their designated pastures \(i\) along a unique, quickest route. Each cow \(i\)'s best route is determined by the unique shortest path from pasture \(1\) to pasture \(i\). However, a mischievous gremlin \(i\) lurks on the final cowpath (edge) of this quickest route, waiting to harass cow \(i\).

To avoid the gremlin, each cow \(i\) must choose an alternative route from pasture \(1\) to pasture \(i\) that does not use the final cowpath of its usual quickest route. Your task is to compute the minimum possible travel time for these alternative routes.

You are given an undirected graph with \(N\) pastures (numbered \(1\) through \(N\)) and \(M\) bidirectional cowpaths (numbered \(1\) through \(M\)). Each cowpath \(i\) connects pastures \(a_i\) and \(b_i\) and requires time \(t_i\) to traverse. It is guaranteed that the unique shortest path (in terms of travel time) from pasture \(1\) to pasture \(i\) is well‐defined for all \(i=2,\dots,N\).

Input Constraints:

• \(2 \le M \le 200\,000\)
• \(3 \le N \le 100\,000\)
• \(1 \le a_i, b_i \le N,\; a_i \neq b_i\)
• \(1 \le t_i \le 1000\)

Note: The forbidden cowpath for cow \(i\) is the one used as the final segment in the unique shortest route from pasture \(1\) to pasture \(i\). The alternative route must avoid this cowpath entirely (regardless of direction).

Example:

// Diagram of the farm:
//   1 --[2]-- 2 -------+
//   |        |        |
//  [2]      [1]      [3]
//   |        |        |
//   +--------3 --[4]-- 4

// Best (quickest) routes without gremlins:
//  p1 to p2: 1 -> 2, best time = 2, forbidden edge: 1->2
//  p1 to p3: 1 -> 3, best time = 2, forbidden edge: 1->3
//  p1 to p4: 1 -> 2 -> 4, best time = 5, forbidden edge: 2->4

// When gremlins are present, alternative routes are:
//  p1 to p2: 1 -> 3 -> 2, total time = 3
//  p1 to p3: 1 -> 2 -> 3, total time = 3
//  p1 to p4: 1 -> 3 -> 4, total time = 6

Your program should output the best travel time for the alternative route for each pasture \(i=2,3,\dots,N\).

inputFormat

The first line contains two integers \(N\) and \(M\) — the number of pastures and the number of cowpaths.

Each of the next \(M\) lines contains three integers \(a_i\), \(b_i\) and \(t_i\) — indicating there is a bidirectional cowpath between pastures \(a_i\) and \(b_i\) with travel time \(t_i\).

outputFormat

For each pasture \(i = 2, 3, \dots, N\), output the minimum travel time of an alternative route from pasture \(1\) to pasture \(i\) that avoids the forbidden cowpath (the last cowpath of the unique, quickest route).

Output each result on a separate line.

sample

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

3
3
6

</p>