블로거 여행자

얀과 타티아나는 여행 블로거가 되어 자기 나라의 도시들을 다니며 영상을 올리기로 했다.

나라에는 1번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있다. 1번 도시는 수도이다. 도시들은 1번부터 $m$번까지 번호가 붙은 $m$개의 양방향 도로로 연결되어 있으며, 각 도로는 서로 다른 두 도시를 잇는다. 같은 두 도시를 여러 도로가 이을 수 있다. 어느 도시에서든 도로를 따라 다른 모든 도시에 갈 수 있다.

두 사람은 수도에서 출발해 다른 도시 중 한 곳으로 갈 계획이지만, 아직 목적지를 정하지 않았다. $k$번 도시로 가는 경로는 도시 $s_1, s_2, \ldots, s_q$와 도로 $r_1, r_2, \ldots, r_{q-1}$로 이루어지며, 다음 조건을 만족해야 한다.

• $s_1 = 1$, $s_q = k$이다.
• 도로 $r_i$는 도시 $s_i$와 $s_{i+1}$을 잇는다.
• 같은 도로를 두 번 지나지 않으므로 모든 $r_i$는 서로 달라야 한다. 같은 도시를 여러 번 지나가도 되며, 출발지인 1번 도시와 도착지인 $k$번 도시를 여러 번 지나가도 된다.

각 도로 $i$에 대해, 그 도로를 촬영한 영상의 길이 $t_i$가 정해져 있다. 여행 중 두 사람은 경로의 도로를 하나씩 골라 영상을 찍는다. 얀은 짧은 영상을 좋아하므로 $t_i$가 가장 작은 도로를 고르고, 타티아나는 긴 영상을 좋아하므로 $t_i$가 가장 큰 도로를 고른다.

두 영상 길이의 합은 $\min\limits_{1 \leq i \leq q-1} t_{r_i} + \max\limits_{1 \leq i \leq q-1} t_{r_i}$이다.

두 사람은 짧은 영상의 인기가 높은 플랫폼에 영상을 올릴 계획이라, 두 영상 길이의 합을 최소로 만들려고 한다. 각 도시 $k$에 대해, 1번 도시에서 $k$번 도시까지 가는 모든 경로 중 합의 최솟값을 구한다.

첫 줄에 두 정수 $n$, $m$ ($2 \leq n \leq 300\,000$, $1 \leq m \leq 300\,000$)이 주어진다. 도시의 수와 도로의 수이다.

다음 $m$개의 줄에는 도로에 대한 정보가 주어진다. $i$번째 줄에는 세 정수 $u_i$, $v_i$, $t_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $0 \leq t_i \leq 10^9$)가 주어진다. 도로가 잇는 두 도시의 번호와 그 도로의 영상 길이이다.

주어진 도로로 어느 도시에서든 다른 모든 도시에 갈 수 있음이 보장된다. 필요하면 다른 도시를 거쳐 갈 수 있다.

각 $2 \leq k \leq n$에 대해, 도시 $k$에서 끝나는 여행에서 두 영상 길이 합의 최솟값을 출력한다.

첫 번째 예시에서 가능한 최적 경로는 다음과 같다.

• $1 \overset{t = 1}{\to} 3 \overset{t = 1}{\to} 2$. 영상 길이 합은 $1 + 1 = 2$이다.
• $1 \overset{t = 1}{\to} 3$. 영상 길이 합은 $1 + 1 = 2$이다.

두 번째 예시에서 가능한 최적 경로는 다음과 같다.

• $1 \overset{t = 2}{\to} 2$. 영상 길이 합은 $2 + 2 = 4$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3$. 영상 길이 합은 $2 + 3 = 5$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5 \overset{t = 4}{\to} 4$. 영상 길이 합은 $2 + 4 = 6$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5$. 영상 길이 합은 $2 + 4 = 6$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5 \overset{t = 4}{\to} 4 \overset{t = 4}{\to} 6$. 영상 길이 합은 $2 + 4 = 6$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 8}{\to} 1 \overset{t = 6}{\to} 7$. 영상 길이 합은 $2 + 8 = 10$이다.

세 번째 예시에서 가능한 최적 경로는 다음과 같다.

• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3 \overset{t = 1}{\to} 4 \overset{t = 3}{\to} 2$. 영상 길이 합은 $0 + 3 = 3$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3$. 영상 길이 합은 $0 + 2 = 2$이다.
• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3 \overset{t = 1}{\to} 4$. 영상 길이 합은 $0 + 2 = 2$이다.