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 contains two integers: $N$ and $M$ ($N \leq 100000$, $M \leq 500000$).
The next $M$ lines each contain three positive integers: $a_i$, $b_i$, and $c_i$, indicating that there is a path of length $c_i$ between vertices $a_i$ and $b_i$, where $c_i \leq 1000$.

Output Format

An integer representing the shortest distance from vertex $1$ to vertex $N$.

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

2

Hint

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