교통 체증

도시 계획가 민아는 N개의 교차로와 M개의 도로로 이루어진 도시의 교통 체증을 분석하고 있다. 각 도로는 방향이 있으며, 이동에 걸리는 시간이 주어진다. 교차로 1번에서 N번까지의 최단 경로를 구하시오.

이동할 수 없는 경우에는 -1을 출력한다.

교차로 지도253411234

입력

첫째 줄에 교차로의 수 N과 도로의 수 M이 공백으로 구분되어 주어진다. 다음 M줄에 도로 정보 u, v, w가 주어진다. 교차로 u에서 v로 이동하는 데 w의 시간이 걸린다.

• 1 ≤ N ≤ 20,000
• 1 ≤ M ≤ 300,000
• 1 ≤ w ≤ 10,000

출력

교차로 1번에서 N번까지의 최단 시간을 출력한다. 이동할 수 없으면 -1을 출력한다.

예제 입력

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

예제 출력

5