J. Takeout Delivering
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Mr. Ham is a very diligent hamster in USTC, and he always uses his weekends to deliver takeout to earn more money.

To maximize his delivery efficiency, he wants to write a program to find the shortest route.

Specifically, we can consider the city Hefei where Mr. Ham is located as an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge has a congestion level $$$w$$$. Mr. Ham starts at vertex $$$1$$$ and wants to deliver the takeout to vertex $$$n$$$. Mr. Ham has found that the delivery time is always determined by the two edges with the highest congestion level along the path. Therefore, Mr. Ham defines the length of a path as the sum of the congestion levels of the two edges with the highest congestion level among the paths. When there is only one edge in the path, the length is defined as the congestion level of that edge.

Now, Mr. Ham wants to know the minimum length of the path from vertex $$$1$$$ to vertex $$$n$$$. Since Mr. Ham doesn't know how to program, he has entrusted this task to you.

Input

The first line contains two integers $$$n$$$ ($$$2\le n \le 3\times 10^5$$$) and $$$m$$$ ($$$\max(1,n-1) \le m \le 10^6$$$), denoting the number of vertices and edges.

The next $$$m$$$ lines contain the edges of the graph, one edge per line. The $$$i$$$-th line contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1\le u_i,v_i\le n,u_i\ne v_i,1\le w_i\le 10^9$$$), indicating an edge $$$(u,v)$$$ which the congestion level is $$$w$$$.

There are no self-loops or multiple edges in the given graph and it is guaranteed that the given graph is connected.

Output

Output a single line containing only one integer, indicating the minimum length of a path from vertices $$$1$$$ to vertices $$$n$$$.

Example
Input
4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9
Output
5