최단 경로 역추적

방향 가중 그래프에서 1번 정점부터 N번 정점까지의 최단 경로 길이와 실제 경로를 출력한다. 가중치는 양수다. 도달할 수 없으면 -1을 출력한다.

다익스트라 실행 중 각 정점의 이전 정점을 기록해 경로를 역추적한다.

입력

첫째 줄에 정점 수 N과 간선 수 M이 주어진다.

다음 M개 줄에 간선의 출발 정점 u, 도착 정점 v, 가중치 w가 주어진다.

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ N×(N-1)
• 1 ≤ w ≤ 1,000

출력

첫째 줄에 최단 경로 길이를 출력한다.

둘째 줄에 경로에 포함된 정점 번호를 공백으로 구분해 출력한다.

도달할 수 없으면 -1을 출력한다.

예제 입력 1

5 7
1 2 3
1 3 5
2 3 1
2 4 6
3 4 2
3 5 8
4 5 4

예제 출력 1

10
1 2 3 4 5