Bessie đang đi du lịch ở Cowland, nơi có \(N\) \((2 \leq N \leq 2 \cdot 10^5)\) thị trấn, được đánh số từ 1 đến \(N\), và \(M\) \((1 \leq M \leq 4 \times 10^5)\) con đường một chiều. Con đường thứ \(i\) chạy từ thị trấn \(a_i\) đến thị trấn \(b_i\) và có nhãn \(l_i\) \((1 \leq a_i, b_i \leq N; 1 \leq l_i \leq 10^9)\).

Một chuyến đi có độ dài \(k\) bắt đầu tại thị trấn \(x_0\) là một dãy các thị trấn \(x_0, x_1, \dots, x_k\), sao cho có một con đường từ thị trấn \(x_i\) đến thị trấn \(x_{i+1}\) đối với mọi \(0 \leq i < k\). Đảm bảo rằng không có chuyến đi nào có độ dài vô hạn trong Cowland và không có hai con đường nào kết nối cùng một cặp thị trấn.

Với mỗi thị trấn, Bessie muốn biết chuyến đi dài nhất có thể bắt đầu từ đó. Đối với một số thị trấn xuất phát, có nhiều chuyến đi dài nhất. Nếu có nhiều chuyến đi dài nhất, Bessie ưu tiên chuyến đi có thứ tự nhãn của các con đường có thứ tự từ điển nhỏ nhất. Một dãy được coi là có thứ tự từ điển nhỏ hơn so với một dãy khác cùng độ dài nếu tại vị trí đầu tiên mà chúng khác nhau, phần tử của dãy đó nhỏ hơn phần tử của dãy còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\), và \(l_i\), biểu thị một con đường từ thị trấn \(a_i\) đến thị trấn \(b_i\) với nhãn \(l_i\).

Output

• In ra \(N\) dòng. Dòng thứ \(i\) phải chứa hai số nguyên cách nhau bởi dấu cách, độ dài và tổng nhãn của chuyến đi ưu tiên của Bessie bắt đầu từ thị trấn \(i\).

Scoring

• Subtask 1: Tất cả các nhãn đường đều giống nhau.
• Subtask 2: Tất cả các nhãn đường đều khác nhau.
• Subtask 3: \(N, M \leq 5000\).
• Subtask 4: Không có giới hạn thêm.

Example

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

0 0
1 10
1 10
2 20

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

0 0
1 10
1 5
2 12

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

0 0
1 10
1 5
2 7

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

0 0
1 5
1 10
2 7