경로

그래프는 노드의 집합과 링크의 집합으로 이루어진다. 링크 하나는 노드 두 개를 잇는다. 그림 1은 노드 4개와 링크 5개로 이루어진 간단한 그래프다. 각 링크에는 출발 노드에서 도착 노드로 향하는 방향이 있고, 비용이 하나씩 붙어 있다. 노드 $m$개는 정수 0, 1, ..., $m-1$로 구분한다.

경로는 링크의 방향을 따라 노드에서 노드로 이동하면서 한 노드를 다른 노드까지 잇는다. 경로의 길이는 사용한 링크의 개수이고, 경로의 비용은 지나간 링크 비용의 합이다. 그래프가 주어졌을 때 노드 0에서 노드 1까지 가는 모든 최단 경로의 비용 가운데 최솟값을 구하라. 비용이 가장 작은 최단 경로를 최소 비용 최단 경로라고 부른다.

그림 1	그림 2

그림 1을 다시 보자. 노드 0에서 노드 1까지 가는 최단 경로는 링크 하나짜리 경로 0 → 1이고 비용은 10이다. 0 → 2 → 1과 0 → 3 → 1은 비용이 더 싸지만 링크를 두 개 쓰므로 더 길다. 그래서 최소 비용 최단 경로는 0 → 1이다.

그림 2에는 길이가 2인 최단 경로가 두 개 있다. 0 → 3 → 1의 비용 4는 0 → 2 → 1의 비용 5보다 작다. 0 → 2 → 3 → 1은 비용이 3으로 더 싸지만 링크를 세 개 쓴다. 그래서 최소 비용 최단 경로는 0 → 3 → 1이다.

첫째 줄에 노드의 개수 $m$과 링크의 개수 $n$이 공백을 사이에 두고 주어진다. 이어지는 $n$개 줄에는 링크 하나의 정보가 정수 세 개로 주어지고, 이웃한 두 정수 사이에는 공백이 하나 있다. 각 줄은 순서대로 출발 노드, 도착 노드, 링크 비용을 뜻한다.

노드는 최대 100개이고 번호는 0번부터 99번까지다. 링크는 최대 1000개이고, 링크 비용은 0 이상 $2^{15} - 1$ 이하이다.

노드 0에서 노드 1까지 가는 최소 비용 최단 경로의 비용을 정수 하나로 출력한다.

최소 비용 최단 경로가 여러 개일 수 있지만, 그 경로들의 비용은 모두 같다.