Problem
Diberikan graf terarah yang boleh mempunyai berbilang tepi dan gelung. Setiap tepi mempunyai berat yang dinyatakan sebagai integer (mungkin negatif). Ia dijamin bahawa tiada kitaran berat negatif.
Anda perlu mengira panjang laluan terpendek dari bucu nombor 1 ke semua bucu lain.
Input
Atur cara mula-mula menerima nombor N (1 <= N <= 100) – bilangan bucu graf dan nombor M (0 <= M <= 10000) – bilangan tulang rusuk. Baris berikut mengandungi M tiga kali ganda nombor yang menerangkan tepi: permulaan tepi, hujung tepi dan berat (berat – ialah integer dari -100 hingga 100).
Output
Atur cara harus mengeluarkan N nombor – jarak dari bucu nombor 1 ke semua bucu graf. Jika tiada laluan ke bucu yang sepadan, cetak nombor 30000 dan bukannya panjang laluan.
Contoh
| # |
Input |
Output |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |