전쟁 - 탈출편 2

전쟁은 막바지에 이르렀고, 당신의 군대는 적국의 수도인 1번 도시 앞까지 진격했다. 승리를 확신하고 총공격 시점을 정하려던 순간, 지금까지의 진격이 적의 유인책이었다는 사실을 알게 되었다.

당신은 군대를 재정비하기 위해 국경 도시인 N번 도시로 돌아가려 한다. 하지만 적은 이 지역의 지리를 잘 알고 있으며, 우리가 최단 경로 중 하나를 선택해 퇴각할 것이라고 예상한다.

따라서 하나 이상의 최단 경로에 포함될 수 있는 도로는 모두 적이 매복할 가능성이 있는 위험한 도로로 본다. 도시와 도시를 잇는 도로 정보가 주어졌을 때, 위험한 도로를 모두 피하면서 1번 도시에서 N번 도시까지 이동하는 최단 시간을 구하라.

첫째 줄에 도시의 수 N(1 <= N <= 1,000)과 도로의 수 M(0 <= M <= 5,000)이 주어진다.

다음 M개 줄에는 정수 a, b, c가 주어진다. 이는 a번 도시와 b번 도시를 잇는 양방향 도로가 있으며, 그 도로를 지나가는 데 c의 시간이 걸린다는 뜻이다.

적이 매복할 가능성이 있는 모든 도로를 피해서 1번 도시에서 N번 도시까지 이동할 때의 최단 시간을 출력한다.