Πλησιάζουν Χριστούγεννα, και ο δήμαρχος της πόλης μελετά τρόπους να την φωταγωγήσει. Μέχρι πέρυσι φωταγωγούνταν όλοι οι δρόμοι. Φέτος αυτό είναι πολυτέλεια, τόσο λόγω των σημαντικών περικοπών στον προϋπολογισμό του δήμου, όσο και λόγω των αντιδράσεων από τις οικολογικές οργανώσεις για κατασπατάληση ενέργειας. Στην προσπάθειά του για εξεύρεση οικονομικότερης λύσης, ο δήμαρχος σκέφτεται να φωταγωγήσει μόνο τις διασταυρώσεις της πόλης. Πιστεύει ότι αυτή η λύση είναι οικονομικότερη, και ότι έτσι ο φωτισμός θα φτάνει σε κάθε δρόμο της πόλης, και θα είναι επαρκής για τη δημιουργία εορταστικής ατμόσφαιρας.

Σας έχει ανατεθεί η τεχνοοικονομική μελέτη για το νέο σχέδιο φωτισμού. Ο Χριστουγεννιάτικος φωτισμός γίνεται ενιαία από μία γεννήτρια που είναι εγκατεστημένη στη διασταύρωση όπου βρίσκεται το δημαρχείο. Πρέπει λοιπόν όλες οι διασταυρώσεις της πόλης να συνδεθούν με την γεννήτρια μέσω ενός συνεκτικού δικτύου καλωδίων που θα εγκατασταθούν σε κάποιους από τους δρόμους της πόλης (όπου ως δρόμος νοείται το τμήμα μιας οδού μεταξύ δύο διαδοχικών διασταυρώσεων). Οι δρόμοι μπορεί να έχουν διαφορετικό μήκος. Όσο μεγαλύτερο είναι το μήκος ενός δρόμου, τόσο μεγαλύτερο είναι το κόστος εγκατάστασης των καλωδίων και η απώλεια ενέργειας σε αυτά. Πρέπει λοιπόν να φτιάξετε ένα πρόγραμμα, που με βάση τα παραπάνω, θα υπολογίζει τις δύο οικονομικά πιο συμφέρουσες λύσεις για την εγκατάσταση καλωδίων ώστε να φωταγωγηθούν όλες οι διασταυρώσεις της πόλης.

Δεδομένα Εισόδου (christmas.in)

Το πρόγραμμά σας θα διαβάζει από το standard input το γράφημα που αντιστοιχεί στο οδικό δίκτυο μιας πόλης. Κάθε διασταύρωση αντιστοιχεί σε μία κορυφή του γραφήματος και κάθε δρόμος σε μία ακμή που συνδέει δύο κορυφές. Όσον αφορά στην μορφή της εισόδου, στην πρώτη γραμμή θα δίνεται το πλήθος N των κορυφών / διασταυρώσεων και το πλήθος M των ακμών / δρόμων. Σε καθεμία από τις υπόλοιπες M γραμμές θα δίνονται τα χαρακτηριστικά μιας ακμής e: πρώτα δύο θετικοί ακέραιοι που αντιστοιχούν στα δύο άκρα της ακμής, και έπειτα ένας θετικός ακέραιος που αντιστοιχεί στο μήκος της d(e).

Δεδομένα Εξόδου (christmas.out)

Το πρόγραμμά σας πρέπει να τυπώνει στο standard output (στην πρώτη γραμμή) δύο ακέραιους χωρισμένους με κενό. Ο πρώτος θα αντιστοιχεί στο συνολικό κόστος της φθηνότερης λύσης και ο δεύτερος στο συνολικό κόστος της δεύτερης φθηνότερης λύσης για την εγκατάσταση καλωδίων που συνδέουν όλες τις διασταυρώσεις της πόλης μεταξύ τους.

Περιορισμοί

3<=N<=2000
3<=M<=10^5
1<=d(e)<=10^9

Bonus:
Δύο επιπλέον παραδείγματα αξιολόγησης με Ν = 50000.
Παράδειγμα εισόδου (αρχείο "christmas.in")

3 3
2 1 67
3 1 46
3 2 75

Παράδειγμα εξόδου (αρχείο "christmas.out")

113 121
Παράδειγμα εισόδου 2 (αρχείο "christmas.in")

5 9
2 1 29
3 2 52
4 1 20
5 3 45
2 5 42
2 4 19
1 5 5
5 4 26
4 3 76

Παράδειγμα εξόδου 2 (αρχείο "christmas.out")

89 95
Παράδειγμα εισόδου 3 (αρχείο "christmas.in")

6 9
1 2 50
1 3 80
2 3 60
2 4 20
3 5 40
2 5 30
4 5 10
4 6 10
5 6 50
Παράδειγμα εξόδου 3 (αρχείο "christmas.out")

130 140