Một khu vực gồm \(n\) trạm phân phối hàng hoá được đánh số từ \(1\) đến \(n\). Trạm \(1\) là trung tâm kho vận, nghĩa là nơi xuất hàng hoá để cung cấp cho các trạm khác.

Có \(m\) con đường, con đường thứ \(i\) nối hai trạm \(u_i\) và \(v_i\) có thời gian di chuyển là \(w_i\). Các con đường này đảm bảo từ một trạm bất kỳ có thể đến một trạm bất kỳ khác qua một hoặc nhiều con đường, và giữa hai trạm có tối đa một con đường nối chúng.

Khi hàng hóa được phát từ trạm \(1\) tới trạm \(i\), thì thời gian dự kiến nhận được hàng bằng thời gian di chuyển nhỏ nhất từ trạm \(1\) tới trạm này.

Do một số lý do như bảo trì hoặc sự cố, một trạm \(x\) nào đó có thể bị gián đoạn hoạt động. Khi đó:

• Trạm \(x\) không nhận được hàng hoá.
• Các con đường nối đến trạm \(x\) cũng không hoạt động.

Từ đó, khi trạm \(x\) bị gián đoạn thì trong \(n\) trạm ban đầu sẽ có những trạm bị ảnh hưởng, tức là thời gian nhận hàng sẽ dài hơn so với dự kiến hoặc không thể nhận hàng.

Là một người quản lý tốt, bạn cần biết với mỗi \(x\) từ \(1\) đến \(n\), khi trạm \(x\) bị gián đoạn thì có bao nhiêu trạm bị ảnh hưởng như đã nói ở trên.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(m\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le m \le 3 \cdot 10^5\)) là số trạm và số con đường.
• Mỗi dòng trong số \(m\) dòng tiếp theo gồm ba số nguyên \(u, v, w\) (\(1 \le u, v \le n; u \neq v; 1 \le w \le 10^9\)) mô tả một con đường.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) chứa một số nguyên là số trạm bị ảnh hưởng khi trạm thứ \(i\) bị gián đoạn.

Constraints

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(m = n - 1\).
• Subtask \(3\) (\(20\%\) số điểm): Mỗi trạm có đúng hai con đường nối đến nó.
• Subtask \(4\) (\(20\%\) số điểm): \(n, m \le 7 \cdot 10^3\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

4
3
2
1

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

6
2
2
1
1
1