안전한 이동

농장에 그렘린들이 들이닥쳤습니다. 이 짓궂고 요정처럼 생긴 생물들은 소들을 괴롭힙니다. 모든 소는 목초지 $1$번에 있는 헛간에서 출발해 각자의 목초지로 이동하며, 소 $i$는 목초지 $1$번에서 목초지 $i$번으로 갑니다.

각 그렘린은 자신이 노리는 소가 평소에 이용하는 유일한 최단 경로를 알고 있습니다. 그렘린 $i$는 목초지 $1$번에서 목초지 $i$번으로 가는 최단 경로의 마지막 간선 한가운데에서 소 $i$를 기다립니다.

소들은 괴롭힘을 피하려고, 목초지 $1$번(헛간)에서 목초지 $i$번으로 가되 그 최단 경로의 마지막 간선을 사용하지 않는 가장 빠른 경로를 새로 고릅니다. 각 소 $i$에 대해, 그렘린 $i$가 지키는 그 간선을 피하면서 목초지 $1$번에서 목초지 $i$번으로 가는 최소 시간을 구하세요.

• 목초지는 $1$번부터 $N$번까지이며 $3 \le N \le 100{,}000$ 입니다.
• 길(간선)은 $1$번부터 $M$번까지이며 $2 \le M \le 200{,}000$ 입니다. 모든 길은 양방향입니다.
• $i$번 길은 목초지 $a_i$와 $b_i$를 잇고, 통과하는 데 $t_i$ 시간이 걸립니다 ($1 \le a_i, b_i \le N$, $1 \le t_i \le 1{,}000$, $a_i \ne b_i$).
• 같은 두 목초지를 잇는 길은 최대 하나이며, 자기 자신으로 돌아오는 길은 없습니다.
• 모든 테스트 데이터에서 목초지 $1$번에서 목초지 $i$번으로 가는 최단 경로는 유일합니다.

예를 들어, 다음과 같은 목초지와 길(대괄호 안의 수는 소요 시간)을 생각해 봅시다.

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

그렘린이 없을 때의 최단 경로는 다음과 같습니다.

그렘린이 각 최단 경로의 마지막 간선을 지킬 때, 그 간선을 피한 최단 경로는 다음과 같습니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$번째 줄까지: 공백으로 구분된 세 정수 $a_i$, $b_i$, $t_i$.

• $N-1$개의 줄을 출력합니다. $i$번째 줄에는 목초지 $1$번에서 목초지 $i+1$번으로 가되, 목초지 $1$번에서 목초지 $i+1$번으로 가는 최단 경로의 마지막 간선을 사용하지 않는 경로의 최소 시간을 출력합니다. 그런 경로가 없으면 그 줄에 $-1$만 출력합니다.