Mô tả bài toán

Trong một thành phố, có ~ N ~ giao lộ được đánh số từ ~ 1 ~ đến ~ N ~. Giao lộ ~ 1 ~ là cửa hàng và giao lộ ~ N ~ là điểm thi đấu trường. Thành phố có ~ M ~ con đường hai chiều giữa các giao lộ, mỗi con đường có độ dài tính bằng phút.

Yêu cầu: Với mỗi bộ dữ liệu đầu vào, hãy tính thời gian ngắn nhất để đi bộ từ cửa hàng (giao lộ ~ 1 ~) đến đấu trường (giao lộ ~ N ~).

Input:

• Dữ liệu gồm nhiều bộ test.
• Mỗi bộ test bắt đầu bằng hai số nguyên ~ N ~ và ~ M ~ (~ 1 \leq N \leq 100, 1 \leq M \leq 10,000 ~).
• Tiếp theo là ~ M ~ dòng, mỗi dòng chứa ba số nguyên ~ A, B, C ~ (~ 1 \leq A, B \leq N, 1 \leq C \leq 1,000 ~):
  • ~ A ~ và ~ B ~: hai giao lộ được nối với nhau.
  • ~ C ~: thời gian để đi bộ giữa ~ A ~ và ~ B ~.
• Một dòng chứa ~ 0 0 ~ kết thúc đầu vào.

Output:

• Với mỗi bộ test, in ra một số nguyên duy nhất là thời gian ngắn nhất để đi bộ từ giao lộ ~ 1 ~ đến giao lộ ~ N ~. Nếu không có đường đi, in ~ -1 ~.

Ví dụ:

Input:

3 3
1 2 1
2 3 1
1 3 3
3 3
1 2 1
2 3 1
3 1 3
0 0

Output:

2
1

Giải thích:

1. Bộ test 1:
   • Đường đi ngắn nhất từ ~ 1 ~ đến ~ 3 ~: ~ 1 \to 2 \to 3 ~ với tổng thời gian ~ 2 ~.
2. Bộ test 2:
   • Đường đi ngắn nhất từ ~ 1 ~ đến ~ 3 ~: ~ 1 \to 3 ~ với tổng thời gian ~ 1 ~.