시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 82 16 13 23.636%

문제

라인 제로 놀이 동산에 새로운 미로가 생겼다. 미로는 방 n개와 방을 연결하는 통로 m개로 이루어져 있다. 통로는 ci 색으로 색칠되어져 있다. 미로는 입구는 1번 방이고, 출구는 n번 방이다. 미로에 들어가려면 헬리콥터를 타고 1번 방으로 낙하해야 한다.

미로를 만든 선영이는 다음날 미로 탈출 대회를 개최하려고 한다. 참가자는 1번 방 에서 출발하고, n번 방에 도착할 때까지 지난 복도의 색상을 모두 종이에 적는다. 대회를 우승하려면 종이에 적은 숫자의 개수가 적어야 한다. 또, 종이에 적은 숫자의 개수가 같은 경우에는 가장 이상적인 경로인 사람이 우승하게 된다. 다른 경로보다 모두 사전 순으로 앞서는 경로를 이상적인 경로라고 한다.

미로의 정보가 주어졌을 때, 1번 방에서 n번 방으로 가는 가장 이상적인 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 방의 수 n과 복도의 수 m이 주어진다. (2 ≤ n ≤ 100,000, 1 ≤ m ≤ 200,000) 다음 m개 줄에는 복도의 정보가 주어지며, 정보는 세 정수 ai, bi, ci로 이루어져 있다. ai와 bi는 복도가 연결하는 방의 번호이고, ci는 복도의 색상이다. (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109) 복도는 양방향이며, 두 방을 연결하는 복도의 개수는 최대 1개이다. 또, 자기 자신으로 되돌아오는 복도가 존재할 수도 있다. 항상 1번 방에서 n번 방으로 갈 수 있는 미로만 입력으로 주어진다.

출력

첫째 줄에 1번 방에서 n번 방으로 가는 최단 경로의 길이를 출력한다. 둘째 줄에는 가장 이상적인 경로의 색을 지나가는 순서대로 출력한다.

예제 입력

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

예제 출력

2
1 3

힌트

수열 (a1, a2, ..., ak)가 수열 (b1, b2, ..., bk)보다 사전 순으로 앞서러면, ai < bi와 모든 j<i에 대해서 aj = bj를 만족하는 i가 존재해야 한다.