1299번 - 전쟁 - 탈출편2

전쟁은 막바지에 치달았다.

당신은 적국의 수도 앞까지 왔다. 전쟁은 거의 승리했다라고 생각했고, 총공격 명령을 내릴 시기를 잡고있던 도중 충격적인 소식을 알게된다.

바로 이렇게 간단히 수도까지 올 수 있었던 것은 승리하고 있던게 아니라, 적의 유인책이었던 것이다.

그 사실을 알고 당신은 군대를 재정비하기 위해서 잠시 군대를 돌려 자신의 국가로 돌아가기로 했다.

그런데 적국의 군대가 만약 군대가 돌아가는 길목에 있다 라면 매우 곤란해 질 수 있다.

적은 분명 지리를 매우 잘 알고 있으므로 (왜냐하면 이곳은 적국이니까.) 분명 우리가 최단거리로 우리 국가로 돌아가는 길목을 막을 것이 분명했다.

하지만 우리는 적의 군대를 피해서 가야만 한다.

도시와 도시를 잇는 도로들이 주어지면, 도로에 매복하는 적을 만나지 않으면서 적국의 수도인 1번 도시로부터 국경도시인 N번 도시까지 가는 경로들 중에 가장 짧은 경로의 길이를 출력하여라.

단, 적은 무조건 우리 군대가 최단경로로 올 것이라 생각하고 어떠한 최단거리로 가도 무조건 막을 수 있는 도로에만 매복할 것이다.

적이 막을 가능성이 있는 모든 도로를 피해서 간다고 할 때, 가장 짧은 경로의 길이를 출력하라.

첫째 줄에는 도시의 수 N(1<=N<=1,000)과 도시를 잇는 도로의 수 M(0<=M<=5,000) 주어진다. 둘째 줄에서 M+1번째 줄 까지는 각각 한 줄마다 a b c가 주어지는데, 이는 a번 도시와 b번 도시를 잇는 도로가 존재하며, 걸리는 시간이 c라는 소리다.

도로에 매복하는 적을 만나지 않으면서 적국의 수도인 1번 도시로부터 국경도시인 N번 도시까지 가는 경로들 중에 가장 짧은 경로의 길이를 출력하여라.