Problem
Um sich auf die Informatik-Olympiade vorzubereiten, beschloss der Bürgermeister, alle Schulen der Stadt mit einer zuverlässigen Stromversorgung zu versorgen. Dazu müssen Sie eine Stromleitung von einer alternativen Stromquelle “Maybutt” zu einer der Schulen der Stadt führen (zu welcher auch immer) und einige Schulen mit Stromleitungen miteinander verbinden.
Es wird angenommen, dass eine Schule eine zuverlässige Stromversorgung hat, wenn sie direkt mit der Quelle "Maybutta" oder mit einer der Schulen verbunden ist, die eine zuverlässige Stromversorgung haben.
Die Kosten für die Verbindung zwischen einigen Schulpaaren sind bekannt. Der Bürgermeister hat beschlossen, eines der beiden wirtschaftlichsten Stromversorgungsschemata auszuwählen (die Kosten des Schemas entsprechen der Summe der Kosten für die Verbindungen von Schulpaaren).
Schreiben Sie ein Programm, das die Kosten für die beiden wirtschaftlichsten alternativen Stromversorgungssysteme von Schulen berechnet.
Eingabe
Die erste Zeile der Eingabedatei enthält zwei natürliche Zahlen, die durch ein Leerzeichen getrennt sind: N (3 <= N <= 100), die Anzahl der Schulen in der Stadt und M – die Anzahl der möglichen Verbindungen zwischen ihnen. Jede der folgenden M Zeilen enthält drei Zahlen: Ai, Bi, Ci, getrennt durch Leerzeichen, wobei Ci Die Kosten für die Verlegung der Stromleitung sind (1<= Ci Die Kosten für die Verlegung der Stromleitung (1<= Ci lt;= 300) von der Schule Ai zur Schule Bi (i=1,2,…,N).
Ausgabe
Die einzige Zeile der Ausgabedatei muss zwei natürliche Zahlen enthalten: S1 und S2, getrennt durch ein Leerzeichen; die beiden kleinsten Schaltungskosten (S1 <= S2). S1=S2 wenn und nur dann, wenn es mehrere zuverlässige Stromversorgungsschaltungen mit den geringsten Kosten gibt.
Es wird garantiert, dass es zwei verschiedene zuverlässige Stromversorgungsschaltungen für die Eingaben gibt.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |