Cho đồ thị vô hướng gồm ~n~ đỉnh và m cạnh, các đỉnh của đồ thị được đánh số thứ tự từ 1 đến ~n~, mỗi cạnh được cho một số nguyên không âm là trọng số của cạnh đó.

Yêu cầu: Hãy cho biết độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh n, biết rằng độ dài của một đường đi là tổng trọng số các cạnh trên đường đi đó.

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên ~n,m~ ~(1≤n≤4000;1≤m≤n^2)~ cho biết số đỉnh và số cạnh của đồ thị.
• ~m~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u,v,c~ cho biết c là trọng số của cạnh ~(u,v)~

Kết quả:

Ghi một số nguyên cho biết kết quả của bài toán. Dữ liệu bài toán luôn đảm bảo có kết quả.

Ví dụ:

Input:

5 7
1 2 2
2 3 1
3 4 1
4 5 4
2 4 3
1 3 4
2 5 10 

Output:

8