Safe Travel

Gremlins have infested the farm. These nasty, fairy-like creatures love to harass the cows. Every cow starts at the barn, conveniently located at pasture $1$, and walks to its own field: cow $i$ travels from pasture $1$ to pasture $i$.

Each gremlin knows the unique shortest route its cow normally takes. Gremlin $i$ waits in the middle of the last road of the shortest route from pasture $1$ to pasture $i$, hoping to harass cow $i$.

To avoid being harassed, each cow $i$ instead picks the fastest route from pasture $1$ (the barn) to pasture $i$ that does not use that last road of its shortest route. For every cow $i$, compute the shortest possible time of such a route that avoids the road guarded by gremlin $i$.

• Pastures are numbered $1$ through $N$, where $3 \le N \le 100{,}000$.
• Roads are numbered $1$ through $M$, where $2 \le M \le 200{,}000$. Every road is bidirectional.
• Road $i$ connects pastures $a_i$ and $b_i$ and takes $t_i$ time to cross ($1 \le a_i, b_i \le N$, $1 \le t_i \le 1{,}000$, $a_i \ne b_i$).
• No two roads connect the same pair of pastures, and no road connects a pasture to itself.
• In every test case, the shortest route from pasture $1$ to pasture $i$ is unique.

For example, consider the following pastures and roads (numbers in brackets are traversal times):

      1--[2]--2-------+
      |       |       |
     [2]     [1]     [3]
      |       |       |
      +-------3--[4]--4

Without gremlins, the shortest routes are:

When each gremlin guards the last road of its cow's shortest route, the best routes that avoid those roads are:

• Line 1: Two space-separated integers $N$ and $M$.
• Lines 2 to $M+1$: Three space-separated integers $a_i$, $b_i$, and $t_i$.

• Print $N-1$ lines. Line $i$ contains the shortest time to travel from pasture $1$ to pasture $i+1$ without using the last road of the shortest route from pasture $1$ to pasture $i+1$. If no such route exists, print $-1$ alone on that line.