계단 보행

시간 제한3초메모리 제한2048 MB

요약
각 정점마다 간선에 적힌 수열이 계단 수열이 되는 1번 정점 출발 보행 중 최단 길이를 구하고, 없으면 -1을 출력한다.
난이도

어려움10점 중 8점

유형
그래프, BFS, 최단 경로, 동적 계획법
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

두 번째 줄부터 MM개의 줄에 각각 간선이 잇는 두 정점 u_iu\_i, v_iv\_i와 간선에 적힌 숫자 x_ix\_i가 공백으로 구분되어 주어집니다.

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

출력

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

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

제한

  • 2≤N≤50 0002 \le N \le 50\ 000
  • 1≤M≤100 0001 \le M \le 100\ 000
  • 1≤u_i,v_i≤N1 \le u\_i, v\_i \le N
  • 1≤x_i≤M1 \le x\_i \le M
  • 하나의 정점을 양끝으로 가지는 간선이 있을 수 있습니다.
  • 어떤 두 정점을 연결하는 간선이 여러 개 있을 수 있습니다.

힌트

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

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

  • 11번 정점: 1→\[]52→\[]43→\[]54→\[]65→\[]53→\[]42→\[]511 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3 \xrightarrow\[]{5} 4 \xrightarrow\[]{6} 5 \xrightarrow\[]{5} 3 \xrightarrow\[]{4} 2 \xrightarrow\[]{5} 1
  • 22번 정점: 1→\[]521 \xrightarrow\[]{5} 2
  • 33번 정점: 1→\[]52→\[]431 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3
  • 44번 정점: 1→\[]52→\[]43→\[]541 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3 \xrightarrow\[]{5} 4
  • 55번 정점: 1→\[]52→\[]43→\[]551 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3 \xrightarrow\[]{5} 5
  • 66번 정점: 1→\[]52→\[]43→\[]54→\[]65→\[]53→\[]42→\[]561 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3 \xrightarrow\[]{5} 4 \xrightarrow\[]{6} 5 \xrightarrow\[]{5} 3 \xrightarrow\[]{4} 2 \xrightarrow\[]{5} 6
  • 77번 정점: 1→\[]52→\[]43→\[]54→\[]65→\[]53→\[]471 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3 \xrightarrow\[]{5} 4 \xrightarrow\[]{6} 5 \xrightarrow\[]{5} 3 \xrightarrow\[]{4} 7
  • 88번 정점: 1→\[]52→\[]43→\[]55→\[]64→\[]581 \xrightarrow\[]{5} 2 \xrightarrow\[]{4} 3 \xrightarrow\[]{5} 5 \xrightarrow\[]{6} 4 \xrightarrow\[]{5} 8
  • 99번 정점: 해당하는 계단 보행이 없습니다.

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

예제1

  1. 예제 1

    입력
    9 9
1 2 5
2 3 4
3 4 5
4 5 6
3 5 5
2 6 5
3 7 4
4 8 5
5 9 3
    예상 출력
    7 1 2 3 3 7 6 5 -1