Problem
Per prepararsi alle Olimpiadi dell'informatica, il sindaco ha deciso di fornire a tutte le scuole della città un'alimentazione elettrica affidabile. Per fare ciò, è necessario condurre una linea elettrica da una fonte alternativa di elettricità “Maibuttya” a una delle scuole della città (non importa quale), oltre a collegare tra loro alcune scuole tramite linee elettriche.
Una scuola è considerata dotata di un'alimentazione elettrica affidabile se è collegata direttamente alla fonte Maibutcha o a una di quelle scuole che dispongono di un'alimentazione elettrica affidabile.
Il costo della connessione tra alcune coppie di scuole è noto. Il sindaco della città ha deciso di scegliere uno dei due schemi di alimentazione elettrica più economici (il costo dello schema è pari alla somma dei costi di collegamento delle coppie di scuole).
Scrivi un programma che calcoli il costo dei due schemi di alimentazione alternativi più convenienti per le scuole.
Input
La prima riga del file di input contiene due numeri naturali separati da uno spazio: N (3 <= N <= 100), il numero delle scuole della città, e M – il numero di possibili connessioni tra di loro. Ognuna delle seguenti righe M contiene tre numeri: Ai, Bi , Ci, separati da spazi, dove Ci - costo di posa di una linea elettrica (1 <= Ci <= 300) dalla scuola Ai alla scuola Bi< /sub > (i=1,2,…,N).
Uscita
La singola riga del file di output deve contenere due numeri naturali S1 e S2 separati da uno spazio &ndash ; i due costi di circuito più bassi (S1 <= S2). S1=S2 se e solo se esistono diversi schemi di alimentazione affidabili a minor costo.
È garantito che esistono due diversi schemi di alimentazione affidabili per i dati di input.
Esempi
| # |
Input |
Uscita |
| 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 |