시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

You are given an undirected graph with $n$ nodes (numbered from $1$ to $n$) and $m$ edges. Each edge has a length. The graph contains neither multiple edges nor self-loops.

Alice and Bob are now trying to play a game. Each player has to pick a path from $1$ to $n$ (not necessary a simple path). The paths have to be different.

Alice always moves first, and she is so clever that she took one of the shortest paths from $1$ to $n$. Now is Bob's turn. Bob wants to pick the shortest possible path from $1$ to $n$ which is different from Alice's path. Your task is to find the length of such path.

Two paths $S$ and $T$ are considered different if and only if they have different number of edges or there is an integer $i$ such that the $i$-th edge of $S$ differs from the $i$-th edge of $T$.

입력

The first line of input contains two integers: the number of nodes $n$ and the number of edges $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$). Each of the next $m$ lines contains three integers $a$, $b$, and $w$ which mean that there is an edge between node $a$ and node $b$, and its length is $w$ ($1 \le a, b \le n$, $1 \le w \le 10^9$). It is guaranteed that there is at least one path from $1$ to $n$.

출력

Print a single line with a single integer: the length of a valid shortest path for Bob.

예제 입력 1

3 3
1 2 1
2 3 4
1 3 3

예제 출력 1

5

예제 입력 2

2 1
1 2 1

예제 출력 2

3