Bài toán: Tối đa tốc độ truyền dữ liệu trong mạng

Bạn được cung cấp một mạng gồm n máy tính và m kết nối. Mỗi kết nối xác định tốc độ tối đa mà một máy tính có thể gửi dữ liệu đến một máy tính khác.

Kotivalo muốn tải xuống dữ liệu từ máy chủ. Hãy xác định tốc độ tối đa mà Kotivalo có thể thực hiện được việc này bằng cách sử dụng các kết nối trong mạng.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: số lượng máy tính và số lượng kết nối.
• Máy tính được đánh số từ ~1, 2, \dots, n~. Máy tính ~1~ là máy chủ và máy tính ~n~ là máy của Kotivalo.
• Sau đó, có ~m~ dòng, mỗi dòng chứa ba số nguyên ~a, b, c~:
  • ~a~: máy tính xuất phát.
  • ~b~: máy tính đích.
  • ~c~: tốc độ tối đa của kết nối từ máy tính ~a~ đến ~b~.

Output:

• In ra một số nguyên duy nhất: tốc độ tối đa Kotivalo có thể tải xuống dữ liệu.

Ràng buộc:

• ~1 \leq n \leq 500~
• ~1 \leq m \leq 1000~
• ~1 \leq a, b \leq n~
• ~1 \leq c \leq 10^9~

Ví dụ chạy:

Input:

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

Output:

6