Problem
情報オリンピックに備えるため、市長は市内のすべての学校に信頼できる電力供給を提供することを決定しました。これを行うには、代替電源「マイブッチャ」から電力線を導く必要があります。市内の学校の 1 つ (どの学校でもかまいません) に接続したり、いくつかの学校を電力線で相互に接続したりします。
学校がマイブッチャ電源に直接接続されている場合、または信頼できる電源を備えている学校のいずれかに接続されている場合、その学校は信頼できる電源を備えていると見なされます。
いくつかのペアの学校間の接続コストは既知です。市長は、2 つの最も経済的な電力供給方式のいずれかを選択することを決定しました (方式のコストは、2 組の学校を接続するコストの合計に等しい)。
学校向けの最も費用対効果の高い 2 つの代替電源スキームのコストを計算するプログラムを作成してください。
入力
入力ファイルの最初の行には、スペースで区切られた 2 つの自然数が含まれています: N (3 <= N <= 100)、市内の学校の数、 M –それらの間の可能な接続の数。次の各 M 行には、3 つの数字が含まれています: Ai、Bi 、Ci、スペースで区切られた Ci - 送電線の敷設コスト(1 <= Ci <= 300) 学校 Ai から学校 Bi< /sub > (i=1,2,…,N).
出力
出力ファイルの 1 行には、2 つの自然数 S1 と S2 が含まれている必要があります。スペース &ndash ; 2 つの最低回線コスト (S1 <= S2)。 S1=S2 最小コストで信頼性の高い電源スキームがいくつかある場合に限ります。
入力データに対して 2 つの異なる信頼性の高い電源方式が存在することが保証されています。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 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 |