You are given a undirected graph with $n$ nodes (numbered from $1$ to $n$) and m edges. Alice and Bob are now trying to play a game.
Both of them will take different route from $1$ to $n$ (not necessary simple).
Alice always moves first and she is so clever that take one of the shortest path from $1$ to $n$.
Now is the Bob's turn. Help Bob to take possible shortest route from $1$ to $n$.
There's neither multiple edges nor self-loops.
Two paths $S$ and $T$ are considered different if and only if there is an integer $i$, so that the $i$-th edge of $S$ is not the same as the $i$-th edge of $T$ or one of them doesn't exist.

The first line of input contains an integer $T\ (1 \leq T \leq 15)$, the number of test cases.

The first line of each test case contains two integers $n, m\ (2 \leq n, m \leq 100,000)$, number of nodes and number of edges. 

Each of the next $m$ lines contains three integers $a, b, w\ (1 \leq a, b \leq n,\ 1 \leq w \leq 10^9)$, this means that there's an edge between node $a$ and node $b$ and its length is $w$.

It is guaranteed that there is at least one path from $1$ to $n$.

Sum of n over all test cases is less than $250,000$ and sum of m over all test cases is less than $350,000$.

For each test case print length of valid shortest path in one line.

5
3

For testcase 1, Alice take path $1 \to 3$ and its length is $3$, and then Bob will take path $1 \to 2 \to 3$ and its length is $54.
For testcase 2, Bob will take route $1 \to 2 \to 1 \to 2$ and its length is $3$