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 \leq n \leq 4000;1 \leq m \leq 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.

Ví dụ:

Input	Output
5 7 1 2 2 2 3 1 3 4 1 4 5 4 2 4 3 1 3 4 2 5 10	8