Roadblocks

베시(Bessie)는 작은 농장으로 이사한 뒤, 가끔 가장 친한 친구를 만나러 옛집으로 걸어갑니다. 도중의 풍경을 즐기고 싶어서 너무 빨리 도착하고 싶지는 않기 때문에, 최단 경로 대신 두 번째로 짧은 경로로 가기로 했습니다. 이러한 경로는 항상 존재한다고 가정합니다.

시골에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 교차로가 있고, 이들을 잇는 $R$개의 양방향 도로가 있습니다. 각 도로는 두 교차로를 연결하며 양의 길이를 가집니다. 베시는 $1$번 교차로에서 출발하고, 친구는 $N$번 교차로에 삽니다.

여기서 경로란 $1$번에서 $N$번으로 가는 임의의 워크(walk)를 말하며, 같은 도로나 교차로를 여러 번 지나도 되고 이미 지난 도로를 되돌아가도 됩니다. 경로의 길이는 지나는 도로들의 길이의 합입니다. 두 번째로 짧은 경로란 그 길이가 최단 경로의 길이보다 엄밀히 크면서, 그러한 모든 경로들 중에서 가장 짧은 경로를 뜻합니다. 즉 최단 경로의 길이를 $L$이라 하면, 답은 $L$보다 엄밀히 큰 값들 중 실제로 만들 수 있는 가장 작은 길이입니다. (길이가 $L$로 같은 서로 다른 경로가 여러 개 있어도 모두 최단 경로로 취급하며, 두 번째로 짧은 길이는 그다음으로 큰 값입니다.)

제약: $1 \le N \le 5000$, $1 \le R \le 100{,}000$입니다.

• 첫째 줄: 두 정수 $N$과 $R$이 공백으로 구분되어 주어집니다.
• 둘째 줄부터 $R+1$번째 줄까지: 각 줄에는 세 정수 $A$, $B$, $D$가 공백으로 구분되어 주어지며, 이는 교차로 $A$와 $B$를 잇는 길이 $D$의 양방향 도로를 나타냅니다 ($1 \le D \le 5000$).

• 교차로 $1$번에서 $N$번까지의 두 번째로 짧은 경로의 길이를 한 줄에 출력합니다.

샘플 그래프에서 최단 경로는 $1 \to 2 \to 4$로 길이가 $100 + 200 = 300$이고, 그다음으로 긴 경로는 $1 \to 2 \to 3 \to 4$로 길이가 $100 + 250 + 100 = 450$입니다. 따라서 두 번째로 짧은 경로의 길이는 $450$입니다.