Description

Teacher Luo is invited to a dance party in city n, while he is currently in city 1. There are many nearby cities numbered 2 to n-1. Some cities are not directly connected by roads, while others are connected by bidirectional roads, and there may even be multiple roads between the same pair of cities.

Given the lengths of the roads between directly connected cities, Teacher Luo wants to know the shortest distance from city 1 to city n.

Input Format

The input consists of n and m, representing n cities and m roads. The following m lines each contain three integers a, b, and c, indicating that there is a road of length c between city a and city b.

Output Format

Output the shortest path from 1 to n. If city n is unreachable from city 1, output -1.

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

90

Hint

【Data Scale and Conventions】
1 ≤ n ≤ 2000
1 ≤ m ≤ 10000
0 ≤ c ≤ 10000