톰에게 쫒기고 있던 제리가 어느 대저택에 숨었다.

톰을 겨우 따돌렸다고 생각한 제리는 저택을 나와 집으로 갈 작정이다.

그런데 이 저택을 나가는 길을 알 수가 없었다.

이 저택에는 방이 N개 있으며, 1, 2, ..., N의 번호가 매겨져있다.

또한 복도가 M개 있고, i(1 ≦ i ≦ M)번 복도는 방 Ai와 방 Bi를 연결한다.

제리는 이 복도를 어느 방향으로든 지나갈 수 있으며 복도 i를 지나는 데는 Di 분 걸린다.

복도 이외에 방과 방 사이를 이동하는 다른 방법은 없다.

이 저택에 있는 방들의 실내 온도는 각각 일정하게 조절되고 있는데,

제리에게는 너무 춥거나 적당하거나, 너무 더운 온도이다.

제리는 갑작스러운 온도 변화에 적응하지 못한다.

마지막에 너무 추운 방을 나오고 나서 X 분 미만 동안 너무 더운 방에 들어갈 수 없다.

마찬가지로 마지막에 너무 더운 방을 나오고 나서 X 분 미만 동안 너무 추운 방에 들어갈 수 없다.

제리는 이동 중에 방에 들어서자마자 방에서 나와야한다. 방주인에게 들키면 잡히기 때문이다.

또한 복도 중간에 되돌아가거나 복도 i를 Di보다 오래 걸쳐 통과 할 수 없다.

그러나 한 번 방문한 방에 다시 들어가거나, 한번 사용한 복도를 다시 사용하는 것은 허용된다.

제리는 현재 방 1에 있다. 이 방은 제리에게 너무 춥다.

제리는 저택의 출구가 있는 N번 방에 도착하면 집에서 탈출 할 수 있다.

제리가 저택을 탈출하는 데 걸리는 최소 시간을 구하라.

입력 예 1을 보면 방을 1 → 2 → 3 → 4 → 5 → 6 → 5 → 8로 이동하는 것이 최소 시간이다.

입력 예 2는 일부 객실의 쌍 (예를 들어 방 1과 방 5)을 연결하는 복도가 여러 개 있다는 것에 유의하라.

길 잃은 제리 timer 2초 memory 512MB

길 잃은 제리 2초 512MB