shiba, một thanh niên hướng nội đã cùng với crush của mình có một buổi đêm giao thừa đầy vui vẻ trong thành phố LQDOJ. Thành phố LQDOJ là một thành phố rộng lớn, có \(N\) giao lộ được đánh số từ \(1\) đến \(N\) và có \(M\) con đường được đánh số từ \(1\) đến \(M\). Mỗi con đường nối liền một cặp giao lộ khác nhau, và không có cặp giao lộ nào được kết nối bởi nhiều hơn một con đường. Từ bất kỳ giao lộ nào, shiba và crush của mình đều có thể đi đến bất kỳ giao lộ khác thông qua các con đường đã cho.

shiba và crush của mình đã cùng nhau khám phá từng ngõ ngách trong thành phố. Tuy nhiên, shiba đã lỡ làm đổ cây kem vào áo của crush khi đang ăn dở cây kem của mình. Điều đó làm crush của shiba giận và bỏ đi trong sự hoảng hốt của shiba. shiba muốn đi tìm crush của mình nhưng anh ấy lại không biết hiện tại cô ấy đang ở đâu, tuy nhiên anh ấy nhận ra rằng mình cùng với cô ấy chắc chắn đã đi qua mọi ngóc ngách trong thành phố, điều này có nghĩa là shiba cùng crush của mình đã đi qua tất cả \(M\) con đường ít nhất một lần, nên shiba chắc chắn rằng crush của mình phải ở đâu đó trong \(M\) con đường ấy.

May mắn thay, shiba có dẫn theo chú chó _minhduc theo trong suốt đêm ấy. Và chú chó ấy có khả năng ghi nhớ rằng con đường thứ \(i\) nối giữa giao lộ \(a_i\) và \(b_i\) đã được đi qua tại thời điểm \(c_i\) (và chú chó ấy có khả năng đánh hơi crush của anh ấy rất tốt). Tuy nhiên khả năng ghi nhớ của _minhduc lại bị rối loạn khiến thứ tự các con đường mà nó đã đi qua được ghi nhớ lại một cách hỗn loạn và đôi khi không đúng logic. Ví dụ, _minhduc nhớ là đã đi qua một con đường tại thời điểm \(10\), nhưng chú chó ấy lại không nhớ mình đã đi qua con đường nào ở thời điểm \(9\).

Người ta có câu "chủ nào, chó nấy". shiba cũng bị trường hợp giống như chú chó của mình 🤡

Tuy trí nhớ rối loạn nhưng shiba là một người thông minh, anh ấy nghĩ ra một kế sách là đi lại từ đầu để nhớ lại hành trình đêm qua mình đã đi những đâu và nhờ _minhduc đánh hơi để tìm crush. shiba bắt đầu cuộc hành trình của mình ở giao lộ \(1\). Vì không muốn lạc đường, shiba sẽ đi qua các con đường theo thứ tự mà thời điểm của con đường tiếp theo phải lớn hơn thời điểm của con đường trước đó (theo trí nhớ của _minhduc). Nói cách khác, nếu shiba đang đi qua một con đường có thời điểm \(c_{current}\), thì thì con đường tiếp theo anh chọn phải có thời điểm \(c_{next} > c_{current}\). Lưu ý rằng anh có thể đi qua một giao lộ nhiều lần.

shiba cần chuyến đi tìm kiếm crush này sẽ có nhiều con đường càng tốt, điều đó giúp tăng tỉ lệ tìm thấy crush của mình hơn nhờ vào việc _minhduc có thể đánh hơi được nhiều hơn. Do đó shiba cần biết số lượng con đường lớn nhất đến từng giao lộ tuân theo quy tắc được nêu trên. Nhưng việc tính toán quá phức tạp, không thể tính nhẩm. Và shiba cũng không mang laptop hay máy tính theo để tính toán số lượng con đường lớn nhất mà anh ấy có thể đi qua từ giao lộ \(1\) tới từng giao lộ khác. Với tư cách là một người có tài năng về code, Bạn hãy giúp shiba giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((2 \le N \le 10^5,1 \le M \le 10^6)\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương lần lượt là \(a_i\), \(b_i\), \(c_i\) \((1 \le a_i,b_i \le N, 1 \le c_i \le 10^9)\).
• Dữ liệu vào luôn đảm bảo rằng \(a_i \neq b_i\) với mọi \(i\).

Output

• In ra \(N\) số nguyên, mỗi số cách nhau một khoảng trắng gồm số con đường lớn nhất mà anh ấy có thể đi qua từ giao lộ \(1\) tới từng giao lộ khác. Nếu không thể đi đến một giao lộ nào đó thì in ra \(0\) để biểu thị rằng không có đường đi nào khả thi đến giao lộ đó.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 10\) và \(M \le 15\).
• Subtask \(2\) (\(20\%\) số điểm): Có \(N \le 10^5\) và \(M = N - 1\).
• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 10^3\) và \(M \le 10^4\).
• Subtask \(4\) (\(10\%\) số điểm): Có \(N \le 10^5\) và \(M \le 3 \times 10^5\) và \(c_i \neq c_j\) với mọi \(i \neq j\).
• Subtask \(5\) (\(10\%\) số điểm): Có \(N \le 10^5\) và \(M \le 3 \times 10^5\).
• Subtask \(6\) (\(10\%\) số điểm): Có \(N \le 10^5\) và \(M \le 10^6\) và \(c_i \neq c_j\) với mọi \(i \neq j\).
• Subtask \(7\) (\(10\%\) số điểm): Không có ràng buộc gì thêm

Example

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

3 3 6 7 8 2 7 4