Tốc Độ Tải Xuống

Có $n$ máy tính và $m$ kết nối mạng một chiều. Máy chủ là máy $1$ và máy đích là máy $n$. Mỗi kết nối từ $a$ đến $b$ có tốc độ tối đa $c$. Hãy tính tốc độ tải xuống tối đa từ máy $1$ đến máy $n$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: ba số nguyên $a$, $b$, $c$, mô tả kết nối từ $a$ đến $b$ với tốc độ $c$.

Dữ liệu ra

In một số nguyên duy nhất là tốc độ tải xuống tối đa.

Ràng buộc

• $1\le n\le 500$
• $1\le m\le 1000$
• $1\le c\le {10}^9$
• Có thể có nhiều kết nối giữa cùng một cặp máy theo cùng một chiều; khi đó tốc độ của chúng được cộng dồn.

Ví dụ