계단 보행 | cho.sh

문제

수열 $a$가 주어질 때, $a$에서 인접한 원소의 차가 모두 $1$이라면 이러한 수열을 계단 수열이라고 합니다. 예를 들어, $[4,5,6,5,6]$과 $[1,2,3,2,1]$은 계단 수열이지만, $[1,2,3,5,4]$나 $[5,4,1,3,2]$는 계단 수열이 아닙니다.

정점 $N$개, 양방향 간선 $M$개로 구성된 그래프가 주어집니다. 그래프의 각 간선에는 $1$ 이상 $M$ 이하의 정수가 하나씩 적혀있습니다.

이 그래프의 정점 $u$에서 하나 이상의 인접한 간선을 따라 이동하는 것을 반복하여 정점 $v$에 도착했을 때, 통과한 간선에 적힌 정수를 나열한 수열이 계단 수열이라면 이를 정점 $u$에서 정점 $v$로 이동하는 계단 보행이라고 합니다. 이때 하나의 정점 또는 간선을 여러 번 사용할 수 있고, 하나의 간선을 여러 번 통과했다면 적힌 정수를 나열할 때에도 간선을 통과할 때마다 적어야 합니다. 이러한 계단 보행이 주어질 때, 그 길이는 이동 중 간선을 통과한 총 횟수로 정의합니다.

이때, 어떠한 보행이 계단 보행이 되기 위해서는 하나 이상의 인접한 간선을 따라 이동해야 함에 유의해야 합니다. 다시 말해, 정점 $u$에서 간선을 따라 이동하지 않고 정점 $u$에 남는 것은 정점 $u$에서 정점 $u$로 이동하는 계단 보행이 아닙니다.

$1 \le i \le N$인 각 정수 $i$에 대해, 그래프의 $1$번 정점에서 $i$번 정점으로 이동하는 계단 보행이 존재하는지 알고자 합니다. 각 정점에 대해 그러한 계단 보행이 존재하는지 판단하고, 존재한다면 그중 가장 짧은 것의 길이를 출력해 주세요.

입력

첫 번째 줄에 정점의 개수 $N$과 양방향 간선의 개수 $M$이 공백으로 구분되어 주어집니다.

두 번째 줄부터 $M$개의 줄에 각각 간선이 잇는 두 정점 $u_i$, $v_i$와 간선에 적힌 숫자 $x_i$가 공백으로 구분되어 주어집니다.

주어진 그래프에는 하나의 정점을 양끝으로 가지는 간선이 있거나 어떤 두 정점을 연결하는 간선이 여러 개 있을 수 있습니다.

출력

총 $N$개의 정수를 한 줄에 공백으로 구분하여 출력합니다. 각각의 값은 다음과 같습니다.

$1$번 정점에서 $i$번 정점으로 이동하는 계단 보행이 존재한다면, $i$번째로 출력되는 정수는 그러한 보행 중 가장 짧은 것의 거리입니다.
$1$번 정점에서 $i$번 정점으로 이동하는 계단 보행이 존재하지 않는다면, $i$번째로 출력되는 정수는 $-1$입니다.

제한

$2 \le N \le 50\ 000$
$1 \le M \le 100\ 000$
$1 \le u_i, v_i \le N$
$1 \le x_i \le M$
하나의 정점을 양끝으로 가지는 간선이 있을 수 있습니다.
어떤 두 정점을 연결하는 간선이 여러 개 있을 수 있습니다.

힌트

예제에서 주어진 그래프는 다음과 같습니다.

각 정점에 대해 $1$번 정점에서 해당 정점으로 이동하는 계단 보행은 다음과 같습니다.

$1$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3 \xrightarrow[]{5} 4 \xrightarrow[]{6} 5 \xrightarrow[]{5} 3 \xrightarrow[]{4} 2 \xrightarrow[]{5} 1$
$2$번 정점: $1 \xrightarrow[]{5} 2$
$3$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3$
$4$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3 \xrightarrow[]{5} 4$
$5$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3 \xrightarrow[]{5} 5$
$6$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3 \xrightarrow[]{5} 4 \xrightarrow[]{6} 5 \xrightarrow[]{5} 3 \xrightarrow[]{4} 2 \xrightarrow[]{5} 6$
$7$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3 \xrightarrow[]{5} 4 \xrightarrow[]{6} 5 \xrightarrow[]{5} 3 \xrightarrow[]{4} 7$
$8$번 정점: $1 \xrightarrow[]{5} 2 \xrightarrow[]{4} 3 \xrightarrow[]{5} 5 \xrightarrow[]{6} 4 \xrightarrow[]{5} 8$
$9$번 정점: 해당하는 계단 보행이 없습니다.

이때 $1$번 정점에서 $1$번 정점으로 이동하는 가장 짧은 계단 보행의 길이가 $0$이 아님에 유의합니다.