Bessie는 작은 농장으로 이사했고 가끔 가장 친한 친구 중 하나를 보러 돌아갑니다. 경치를 좋아해 옛집에 너무 빨리 도착하고 싶지 않아 최단 대신 두 번째로 짧은 길을 택합니다. 그런 길은 반드시 있음을 압니다.

양방향 도로 $R$개($1 \le R \le 100,000$)가 있고 각각 교차로 $N$개($1 \le N \le 5000$) 중 둘을 잇습니다. 번호는 $1..N$이고 출발은1, 친구와 목적지는 $N$입니다.

두 번째 길은 어떤 최단 길과도 도로를 공유하고 되돌아가 같은 도로나 교차로를 여러 번 써도 됩니다. 최단 길보다 긴 길 중 최단입니다. 여러 최단 길이 있으면 그들보다 길지만 다른 어떤 길보다 길지 않습니다.

입력

1행: 공백으로 구분한 두 정수 $N$와 $R$.

$2..R+1$행: 공백으로 구분한 세 정수 $A$, $B$, $D$으로 $A$와 $B$를 잇는 길이 $D$($1 \le D \le 5000$)인 도로를 나타냅니다.

출력

1행:1에서 $N$까지 두 번째로 짧은 길 길이.

예제

입력 1

4 4
1 2 100
2 4 200
2 3 250
3 4 100

출력 1

450

참고

힌트

두 경로: $1 \to 2 \to 4$(길이 $100+200=300$)와 $1 \to 2 \to 3 \to 4$(길이 $100+250+100=450$).