문제
그래프가 주어졌을 때 1번 정점에서 출발해서 N번 정점으로 도착하는 경로 중에서 가장 짧고 사전순으로 가장 빠른 경로를 찾는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 정점 개수 N과 간선의 개수 M이 주어진다. 그 다음 M개 줄에 걸쳐 간선에 대한 정보가 a b d 형태로 주어진다. a와 b는 연결된 두 정점의 번호이고, d는 그 간선의 거리이다. 간선은 양방향으로 연결되어 있고, 두 정점 사이에 여러개의 간선이 존재하지 않는다.
2≤N≤1000 1≤M≤N*(N-1)/2 1≤a, b≤N 1≤d≤10
출력
첫 번째 줄에는 1번부터 N번까지의 최단 거리를 출력하고, 두 번째 줄에는 방문하는 도시의 번호를 순서대로 출력한다. 각 번호 사이에는 공백을 하나 넣는다.
예제
5 6
1 2 3
1 3 4
2 4 3
3 4 1
3 5 2
5 4 1
6
1 3 4 5
로그인해야 코드를 작성할 수 있어요.