Xét một mạng gồm \(n\) máy tính và \(m\) kết nối. Mỗi kết nối chỉ định tốc độ 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 một số dữ liệu từ máy chủ. Tốc độ tối đa mà anh ta có thể làm điều này, sử dụng các kết nối trong mạng là bao nhiêu?

Translator's note: bạn có thể quy tốc độ về đơn vị: ví dụ số MB/s. Vậy tốc độ của một phương án sẽ là tổng dung lượng của các đường truyền khác nhau tính theo đơn vị đó.

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(m\): số lượng máy tính và kết nối. Các máy tính được đánh số \(1,2,\ldots, n\). Máy tính \(1\) là máy chủ và máy tính \(n\) là máy tính của Kotivalo.
• Sau đó, có \(m\) dòng mô tả các kết nối. Mỗi dòng gồm ba số nguyên \(a, b\) và \(c\): máy tính \(a\) có thể gửi dữ liệu đến máy tính \(b\) với tốc độ \(c\).

Output

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

Giới hạn

• \(1 \le n \le 500\)
• \(1 \le m \le 1000\)
• \(1 \le a, b \le n\)
• \(1 \le c \le 10^9\)

Example

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

6