Problem A: Travel

Problem A: Travel

Time Limit: 1 Sec  Memory Limit: 1024 MB
Submit: 4101  Solved: 755
[Submit][Status][Web Board]


There are n cities and m roads, and each road has a length. These n cities are numbered from 1 to n. Please find the shortest path from city_1 to city_n.


The first line contains two integers n, m \((1\leq n, m \leq 10^5)\), indicating that there are n cities, m roads.

The next m lines, each line contains 3 integers, u, v, w \((1\leq u, v \leq n, 1\leq w \leq 10^9)\), indicating that there is a unidirectional road from u to v, cost w.


Please output the minimum cost from city_1 to city_n in one line. If there is not exist a road from city_1 to city_n, please output -1.

Sample Input

3 3
1 2 2
2 3 1
1 3 1

Sample Output