느리게 가기

슬로우 타운에는 1번부터 N번까지 번호가 붙은 N개의 교차점이 있고, M개의 양방향 도로가 서로를 연결한다. 어떤 교차점에서든 하나 이상의 도로를 지나면 다른 모든 교차점에 도달할 수 있다. 교차점 uj와 교차점 vj를 연결하는 j번째 도로를 지나는 데 걸리는 시간은 tj 단위다.

안디는 1번 교차점에 살고 사무실은 N번 교차점에 있다. 안디는 항상 정해진 시각에 집을 나서며, 사무실에 최대한 일찍 도착할 수 있는 경로로 간다. 안디의 상사 부디는 안디가 항상 사무실에 너무 일찍 도착해서 경비원들과 문제가 생긴다는 것을 안다. 부디는 안디가 느리게 가서 평소보다 적어도 1 단위 시간 늦게 사무실에 도착하기를 바란다. 그러나 안디는 정해진 시각에 나가서 최대한 일찍 도착하는 습관을 바꾸지 않으려 해서 둘 사이의 협상은 실패로 끝난다.

부디의 상사 찬드라는 안디를 바꿀 수 없다면 도로를 바꿔서 안디의 이동 시간을 늘리면 어떻겠냐고 생각한다. 찬드라는 시청에 영향력이 있어서 그것이 가능하다.

구체적으로, 찬드라는 j번째 도로를 지나는 데 걸리는 시간을 tj에서 tj보다 큰 임의의 정수로 바꿀 수 있다. 새로 바뀐 이동 시간을 t'j라 하면, j번째 도로의 이동 시간을 tj에서 t'j로 바꾸는 비용은 t'j − tj다.

부디는 필요한 정보를 모두 모았고, 이제 안디의 집에서 사무실까지의 최단 이동 시간이 적어도 1 단위 시간만큼 늘어나도록 도로를 바꾸는 데 필요한 최소 총비용을 계산해야 한다. 이 사무실의 새 인턴으로서 부디가 최소 총비용을 계산하도록 도와라.

예를 들어, N = 7개의 교차점과 M = 8개의 도로가 있는 다음 마을을 보자. 안디의 집은 1번 교차점에, 사무실은 7번 교차점에 있다. 이 마을에서 안디는 집에서 사무실까지 가는 데 최소 11 단위가 필요하다. 예를 들어 1 → 2 → 5 → 7 또는 1 → 4 → 6 → 7 경로로 총 11 단위가 걸린다.

부디가 안디가 평소보다 적어도 1 단위 시간 늦게 도착하기를 바란다면, 안디의 집에서 사무실까지 가는 모든 경로의 이동 시간이 적어도 11 + 1 = 12 단위여야 한다. 이를 달성하는 방법은 여러 가지다. 예를 들어 도로 (1, 2)의 이동 시간을 2에서 3으로, 도로 (1, 4)의 이동 시간을 3에서 4로 바꾸면 총비용은 1 + 1 = 2다. 또는 도로 (2, 5)의 이동 시간을 4에서 5로, 도로 (6, 7)의 이동 시간을 2에서 3으로 바꿔도 총비용은 1 + 1 = 2다. 다른 해법도 많다. 이 예에서 부디의 바람을 만족하도록 도로를 바꾸는 최소 총비용은 2다.

첫 줄에 두 정수 N M (2 ≤ N ≤ 1000; 1 ≤ M ≤ 20 000)이 주어진다. 각각 슬로우 타운의 교차점 수와 도로 수다. 다음 M개 줄에 각각 세 정수 uj vj tj (1 ≤ uj < vj ≤ N; 1 ≤ tj ≤ 106)가 주어진다. 각각 슬로우 타운의 양방향 도로와 그 이동 시간이다. 어떤 교차점 쌍을 연결하는 도로도 최대 하나이며, 어떤 교차점에서든 하나 이상의 도로를 지나 다른 모든 교차점에 도달할 수 있음이 보장된다.

안디의 집에서 사무실까지의 이동 시간이 적어도 1 단위 시간만큼 늘어나도록 도로를 바꾸는 데 필요한 최소 총비용을 한 줄에 정수로 출력한다.