Octagon phụ trách nhiều cơ sở có tầm quan trọng chiến lược, như hầm phóng tên lửa, ra-đa, nhà ăn, văn phòng cựu chiến binh, kho quân phục, … Việc bảo vệ mạng lưới kết nối giữa các cơ sở này là vô cùng quan trọng, nhưng mặt khác, mối đe dọa đối với mạng lưới cũng cần được giảm thiểu. Với mỗi con đường hai chiều nối các cơ sở khác nhau, người ta đã xác định Hệ số Đe dọa Tấn công (thường gọi là hệ số). Johnny, người mới được Octagon tuyển dụng, ngay cả lúc nửa đêm cũng có thể tính một tập con các con đường sao cho tổng hệ số nhỏ nhất mà vẫn cho phép di chuyển giữa mọi cặp cơ sở; ta gọi một con đường thuộc ít nhất một tập con như vậy là đường then chốt.

Tuy nhiên, không có gì là chắc chắn: các hệ số có thể thay đổi. Trong đợt đánh giá hằng năm, Octagon quyết định tính cho mỗi con đường giá trị $x$ lớn nhất sao cho khi đặt hệ số của nó bằng $x$ (và giữ nguyên mọi hệ số khác), con đường này là đường then chốt. Nhiệm vụ được giao cho Johnny, người không được phép sai sót trong một việc quan trọng như vậy.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), cách nhau bởi một dấu cách, lần lượt biểu thị số cơ sở do Octagon giám sát và số con đường hai chiều giữa chúng. Các cơ sở được đánh số bằng các số tự nhiên liên tiếp từ $1$ đến $n$.

Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $a$, $b$ và $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), cách nhau bởi một dấu cách, mô tả một con đường hai chiều giữa cơ sở $a$ và $b$ với hệ số $c$. Mỗi cặp không thứ tự $\{a,b\}$ xuất hiện nhiều nhất một lần.

Các con đường hiện có luôn cho phép di chuyển giữa hai cơ sở bất kỳ.

Dữ liệu ra

Bạn cần in $m$ dòng, mỗi dòng ứng với một con đường trong dữ liệu vào, theo đúng thứ tự được cho. Ở dòng ứng với một con đường, in một số tự nhiên: giá trị lớn nhất sao cho sau khi thay hệ số của con đường bằng giá trị này (và giữ nguyên các hệ số khác), nó là đường then chốt. Nếu giá trị này lớn hơn $10^9$ hoặc có thể lớn tùy ý, hãy in $10^9$.

Ví dụ

Dữ liệu vào 1

6 7
1 2 2
2 3 1
3 4 0
1 4 3
3 5 20
4 5 8
3 6 14

Dữ liệu ra 1

3
3
3
2
8
20
1000000000

Ghi chú

Mạng lưới đường trong ví dụ có dạng như sau: