문제

최단 거리를 구하는 알고리즘을 잘 작성하셨는데, 최단 경로는 어떻게 구하나요? -이종률 교수님-

$N$개의 정점과 $M$개의 유향 간선으로 이루어진 그래프가 주어진다. 각 정점에는 $1$부터 $N$까지 번호가 매겨져 있고, 각 간선에는 음이 아닌 정수 가중치가 부여되어 있다.

이 그래프에서 $1$번 정점에서 $N$번 정점으로 가는 최단 경로를 구해보자. 최단 거리는 유일하지만, 최단 경로는 여러 개가 있을 수도 있음에 유의하자.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($2\le N\le 100\,000;\ 1\le M\le 300\,000$)

둘째 줄부터 $M$개의 줄에 걸쳐 각 줄에 각 간선이 연결하는 두 정점 $u$, $v$와 가중치 $w$가 공백으로 구분되어 주어진다. ($1\le u, v\le N;\ u\neq v; 0\le w\le 10^9$)

두 정점을 연결하는 간선이 여러 개 주어질 수도 있음에 유의하자.

출력

$1$번 정점에서 $N$번 정점으로 가는 최단 경로에서 거치는 정점이 $1$, $A$, $B$, $C$, $N$라면, 1 -> A -> B -> C -> N처럼 출력한다. 만약 $1$번 정점과 $N$번 정점 사이에 경로가 존재하지 않는다면 대신 -1를 출력한다.

정답이 여러 개라면 그 중 하나만 출력한다.

예제 입력 1

7 9
1 2 3
2 3 1
4 2 1
3 6 3
6 7 2
1 4 0
7 1 4
5 4 8
1 6 10

예제 출력 1

1 -> 4 -> 2 -> 3 -> 6 -> 7

예제 입력 2

5 5
1 2 2
1 3 1
3 4 1
2 5 1
4 5 1

예제 출력 2

1 -> 3 -> 4 -> 5

1 -> 2 -> 5도 정답으로 인정된다.

노트

출제자는 교수님의 질문에 답하지 못했다..