이상적인 경로

놀이공원에 방 n개와 방을 잇는 양방향 통로 m개로 이루어진 미로가 새로 생겼다. 각 통로에는 색 ci가 칠해져 있다. 미로의 입구는 1번 방이고, 출구는 n번 방이다.

미로 탈출 대회의 참가자는 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 ≤ 10^9)

모든 통로는 양방향이다. 두 방을 잇는 통로가 여러 개일 수도 있고, 같은 방으로 되돌아오는 통로(ai = bi)가 있을 수도 있다. 입력으로는 항상 1번 방에서 n번 방으로 갈 수 있는 미로만 주어진다.

첫째 줄에 1번 방에서 n번 방으로 가는 최단 경로의 길이(지나는 통로의 수)를 출력한다.

둘째 줄에 가장 이상적인 경로가 지나는 통로의 색을 순서대로 공백으로 구분해 출력한다.

수열 (a1, a2, ..., ak)가 수열 (b1, b2, ..., bk)보다 사전 순으로 앞선다는 것은, 어떤 위치 i가 존재하여 ai < bi이고 그보다 앞선 모든 위치 j < i에서 aj = bj를 만족하는 경우를 뜻한다.