City Roads

Problem Background

Special for beginners, ^_^

Problem Description

Teacher Luo is invited to a dance in city $n$, while the city he is currently in is city $1$. There are many other cities $2 \sim n-1$ nearby. Some pairs of cities are not directly connected by a road, while some are, and these roads are bidirectional (there may also be multiple roads between the same pair of cities).

Given the lengths of the directly adjacent city roads, Teacher Luo wants to know the shortest distance from city $1$ to city $n$.

Input Format

The input gives $n, m$, representing $n$ cities and $m$ roads.

The following $m$ lines each contain three integers a b c, meaning there is a road of length $c$ between city $a$ and city $b$.

Output Format

Output the shortest distance from $1$ to $n$. If $1$ cannot reach $n$, output $-1$.

Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

Sample Output

90

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case. $1 \le n \le 2000$, $1 \le m \le 10000$, $0 \le c \le 10000$.