Băng Thông Cực Đại

Có $n$ máy chủ và $m$ kết nối một chiều. Kết nối $a->b$ truyền được nhiều nhất $c$ đơn vị dữ liệu trong một giây. Dữ liệu bắt đầu ở máy $1$ và cần đến máy $n$; nó có thể được chia thành nhiều phần và đi qua nhiều tuyến.

Một máy trung gian không được tạo thêm hay làm mất dữ liệu: tổng tốc độ nhận vào phải bằng tổng tốc độ gửi đi. Hãy xác định tốc độ tải lớn nhất có thể duy trì.

Input

• Dòng đầu chứa $n$ và $m$.
• Mỗi trong $m$ dòng tiếp theo chứa $a,b,c$, biểu diễn một kết nối từ $a$ đến $b$ có băng thông $c$.

Output

• In tốc độ truyền lớn nhất từ máy $1$ đến máy $n$.

Constraints

• $2\le n\le 500$.
• $1\le m\le 1000$.
• $1\le a,b\le n$.
• $1\le c\le 10^9$.
• Nhiều kết nối cùng hướng giữa hai máy được phép xuất hiện.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 30$ và $m\le 100$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 7
1 2 4
1 3 7
2 4 3
3 2 2
3 4 4
4 5 6
2 5 1

7