Octagon bertanggung jawab atas banyak fasilitas strategis, seperti silo rudal, radar, kantin, kantor veteran, gudang seragam, … Sangat penting untuk mengamankan jaringan penghubung antarfasilitas tersebut, tetapi di sisi lain ancaman terhadap jaringan ini harus diminimalkan. Untuk setiap jalan dua arah yang menghubungkan fasilitas berbeda, ditentukan Koefisien Ancaman Serangan (biasa disebut koefisien). Johnny, yang baru dipekerjakan Octagon, bahkan pada tengah malam dapat menghitung suatu himpunan bagian jalan yang meminimalkan jumlah koefisien dan tetap memungkinkan perjalanan antara setiap pasang fasilitas; jalan yang terdapat dalam setidaknya satu himpunan bagian seperti itu disebut jalan kunci.

Namun, tidak ada yang bisa dianggap pasti: koefisien dapat berubah. Sebagai bagian dari evaluasi tahunan, Octagon memutuskan untuk menghitung, bagi setiap jalan, nilai $x$ tertinggi sehingga ketika koefisiennya diubah menjadi $x$ (dan semua koefisien lain dibiarkan seperti semula), jalan tersebut merupakan jalan kunci. Tugas ini diberikan kepada Johnny, yang tidak boleh keliru dalam urusan sepenting ini.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), dipisahkan oleh satu spasi, yang masing-masing menyatakan jumlah fasilitas di bawah pengawasan Octagon dan jumlah jalan dua arah di antaranya. Fasilitas diberi nomor dengan bilangan asli berurutan dari $1$ hingga $n$.

Masing-masing dari $m$ baris berikutnya berisi tiga bilangan bulat: $a$, $b$, dan $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), dipisahkan oleh satu spasi, yang menggambarkan jalan dua arah antara fasilitas $a$ dan $b$ dengan koefisien $c$. Setiap pasangan tak berurutan $\{a,b\}$ muncul paling banyak sekali.

Jalan yang ada selalu memungkinkan perjalanan antara dua fasilitas mana pun.

Keluaran

Cetak $m$ baris, satu untuk setiap jalan pada masukan, dengan urutan yang sama seperti pada masukan. Pada baris untuk suatu jalan, cetak satu bilangan asli: nilai maksimum sehingga setelah koefisien jalan diubah menjadi nilai tersebut (dan koefisien lainnya tetap), jalan itu merupakan jalan kunci. Jika nilainya lebih besar dari $10^9$ atau dapat sebesar apa pun, cetak $10^9$.

Contoh

Masukan 1

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

Keluaran 1

3
3
3
2
8
20
1000000000

Catatan

Jaringan jalan pada contoh tampak sebagai berikut: