Problem
Untuk membuat persediaan menghadapi Olimpik dalam Informatik, Datuk Bandar memutuskan untuk menyediakan semua sekolah di bandar dengan bekalan kuasa yang boleh dipercayai. Untuk melakukan ini, adalah perlu untuk menjalankan talian kuasa daripada sumber elektrik alternatif “Maibuttya” ke salah satu sekolah di bandar (tidak kira yang mana satu), serta menghubungkan beberapa sekolah antara satu sama lain melalui talian elektrik.
Sebuah sekolah dianggap mempunyai bekalan kuasa yang boleh dipercayai jika ia disambungkan terus ke sumber Maibutcha atau ke salah satu sekolah yang mempunyai bekalan kuasa yang boleh dipercayai.
Kos sambungan antara beberapa pasangan sekolah diketahui. Datuk Bandar bandar memutuskan untuk memilih salah satu daripada dua skim bekalan kuasa yang paling menjimatkan (kos skim itu adalah sama dengan jumlah kos menyambung pasangan sekolah).
Tulis program yang mengira kos dua skim bekalan kuasa alternatif yang paling kos efektif untuk sekolah.
Input
Baris pertama fail input mengandungi dua nombor asli yang dipisahkan oleh ruang: N (3 <= N <= 100), bilangan sekolah di bandar dan M – bilangan sambungan yang mungkin antara mereka. Setiap baris M berikut mengandungi tiga nombor: Ai, Bi , Ci, dipisahkan dengan ruang, di mana Ci - kos memasang talian kuasa (1 <= Ci <= 300) dari sekolah Ai ke sekolah Bi< /sub > (i=1,2,…,N).
Output
Barisan tunggal fail output mesti mengandungi dua nombor asli S1 dan S2 dipisahkan oleh ruang &ndash ; dua kos litar terendah (S1 <= S2). S1=S2 jika dan hanya jika terdapat beberapa skim bekalan kuasa yang boleh dipercayai dengan kos paling rendah.
Adalah dijamin bahawa terdapat dua skim bekalan kuasa boleh dipercayai yang berbeza untuk data input.
Contoh
| # |
Input |
Output |
| 1 |
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121 |