Shortest Path in a Weighted Undirected Graph

Special for beginners, ^_^

Problem Description

Given a weighted undirected graph with $M$ edges and $N$ vertices. Find the shortest path from vertex $1$ to vertex $N$.

Input Format

The first line: $N,M$ ($N\le100000$, $M\le500000$).

The next $M$ lines each contain $3$ positive integers $a_i,b_i,c_i$, meaning there is a road of length $c_i$ between $a_i$ and $b_i$, with $c_i\le1000$.

Output Format

One integer: the shortest distance from $1$ to $N$.

Sample Input 1

4 4
1 2 1
2 3 1
3 4 1
2 4 1

Sample Output 1

2

Hint

Note that the graph may contain multiple edges and self-loops. The data guarantees that there is a path connecting $1$ to $N$.

Constraints

1s, 1024KiB for each test case.