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.