Đất nước xyz tươi đẹp là nơi khởi nguồn của lễ hội kẹo. Vào ngày này, người ta thường đặt kẹo ở ngoài đường để chờ một con sói – con vật linh thiêng của họ đến ăn. Đất nước gồm \(n\) thành phố, đánh số từ 1 đến \(n\). Có \(m\) con đường đánh số từ 1 đến \(m\), con đường thứ \(i\) được đặc trưng bởi 3 số nguyên: \(u_i, v_i, w_i\) cho phép đi theo một chiều từ \(u_i\) đến \(v_i\), và người ta đặt \(w_i\) viên kẹo trên con đường này

Con sói sẽ xuất hiện ở một thành phố nào đó, nó sẽ di chuyển theo các con đường và ăn hết kẹo trên đường nó đi qua (có thể đi qua mỗi thành phố, mỗi con đường nhiều lần). Nó muốn biết với mỗi thành phố mà nó giả định chọn làm nơi xuất phát thì nó có thể ăn nhiều nhất được bao nhiêu viên kẹo?

Input

• item Dòng đầu tiên chứa \(n,m\) là số thành phố và số đường một chiều
• item \(m\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u,v,w\)

Output

• Gồm \(n\) dòng, dòng thứ \(i\) là số viên kẹo nhiều nhất sói có thể ăn nếu chọn \(i\) làm thành phố xuất phát

Scoring

• \(1 \leq n, m \leq 10^5\)
• Subtask \(1\) (\(50\%\) số điểm): \(1 \leq n \leq 1000\)
• Subtask \(2\) (\(50\%\) số điểm): không có điều kiện gì thêm

Example

11 14
4 5 1
3 1 1
2 3 1
3 4 1
5 4 1
4 9 1
10 11 1
8 7 1
6 8 1
7 6 1
8 11 1
7 4 1
1 2 1
11 10 5 

7
7
7
3
3
10
10
10
0
6
6