Miliarder Christian hari ini mempelajari algoritma Dijkstra dengan potensial Johnson. Ia sangat menyukainya sehingga memutuskan menambahkan potensial ke semua graf favoritnya. Selera Christian sangat unik: ia hanya menyimpan graf berarah berbobot di kamar rahasianya.

Mari ingat kembali cara kerja potensial. Setiap simpul $v$ diberi sebuah potensial, yaitu bilangan real $\varphi(v)$. Jika sebelumnya ada sisi dari $u$ ke $v$ dengan bobot awal $w$, bobot barunya menjadi $w'=w-\varphi(v)+\varphi(u)$.

Kekuatan graf didefinisikan sebagai nilai minimum bobot sisi-sisinya. Christian tidak ingin graf lemah berada di kamarnya, sehingga ia ingin memilih potensial agar kekuatan graf maksimum. Bantulah ia.

Masukan

Baris pertama berisi dua bilangan bulat $n$ ($2\le n\le1000$) dan $m$ ($1\le m\le100\,000$), yaitu banyak simpul dan sisi graf favorit Christian. Masing-masing dari $m$ baris berikutnya berisi tiga bilangan bulat $u_i,v_i,w_i$ yang mendeskripsikan sisi: titik awal, titik akhir, dan bobotnya, secara berurutan ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).

Keluaran

Baris pertama harus berisi kekuatan maksimum graf. Jika jawaban dapat dibuat tak terbatas besarnya, keluarkan string “+inf” sebagai gantinya.

Jika jawabannya berhingga, baris kedua harus berisi $n$ bilangan real, yaitu potensial simpul-simpul. Nilai mutlak setiap bilangan tidak boleh melebihi $10^{10}$. Selisih jawabanmu terhadap jawaban benar, dan terhadap jawaban yang dihitung berdasarkan potensial yang kamu berikan, masing-masing tidak boleh melebihi $10^{-5}$.

Contoh

Masukan 1

3 3
1 2 1
2 3 1
3 1 1

Keluaran 1

1.0
0.0 0.0 0.0

Masukan 2

2 1
1 2 1

Keluaran 2

+inf