Mountains and Valleys

Σχεδιάζετε ένα μακρύ πεζοπορικό ταξίδι σε κάποιο ενδιαφέρων, αλλά πολύ γνωστό έδαφος. Υπάρχουν ~N~ ενδιαφέρουσες τοποθεσίες που θα θέλατε να επισκεφτείτε και ~M~ μονοπάτια που συνδέουν ζεύγη τοποθεσιών. Κάθε μονοπάτι έχει έναν βαθμό δυσκολίας που υποδεικνύεται ως ένας θετικός ακέραιος αριθμός.

Το σύστημα μονοπατιών είναι λίγο ιδιαίτερο ωστόσο. Υπάρχουν ακριβώς ~N - 1~ μονοπάτια με βαθμό δυσκολίας ~1~ (αυτά είναι εντελώς επίπεδα μονοπάτια) και όλα τα υπόλοιπα μονοπάτια έχουν βαθμό δυσκολίας τουλάχιστον ⌈~N~/~3~⌉ (αυτά είναι πολύ ορεινά μονοπάτια). (Η οροφή του ~x~, που συμβολίζεται με ⌈~x~⌉), είναι ο μικρότερος ακέραιος ο οποίος είναι μεγαλύτερος ή ίσος του ~x~).

Επιπλέον, είναι πιθανό να ταξιδέψετε μεταξύ δύο οποιονδήποτε τοποθεσιών χρησιμοποιώντας μόνο τα μονοπάτια με επίπεδο δυσκολίας ~1~.

Θα θέλατε να επισκεφθείτε κάθε τοποθεσία, ξεκινώντας τον περίπατό σας από οποιαδήποτε τοποθεσία της επιλογής σας και τελειώνοντας σε κάποια άλλη τοποθεσία, έτσι ώστε να έχετε επισκεφθεί κάθε τοποθεσία τουλάχιστον μία φορά και το τελικό άθροισμα των επιπέδων δυσκολίας να είναι το ελάχιστο ανάμεσα σε όλους τους περιπάτους. Σημειώστε ότι το να περπατάτε ένα μονοπάτι ~k~ φορές με επίπεδο δυσκολίας ~d~ συνεισφέρει μια τιμή ~k~ ~\cdot~ ~d~ στο άθροισμα των επιπέδων δυσκολίας.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο, χωρισμένους με κενό, ακέραιους ~N~ (~4~ ~\le~ ~N~ ~\le~ ~500\,000~) και ~M~ (~N-1~ ~\le~ ~M~ ~\le~ ~2\,000\,000~).

Οι επόμενες ~M~ γραμμές περιέχουν τρεις, χωρισμένους με κενό, ακέραιους ~x_i~, ~y_i~ και ~w_i~ που περιγράφουν το μονοπάτι μεταξύ των τοποθεσιών ~x_i~ και ~y_i~ με επίπεδο δυσκολίας ~w_i~ (~1~ ~\le~ ~i~ ~\le~ ~M~, ~0~ ~\le~ ~x_i~,~y_i~ ~\le~ ~N - 1~, ~x_i~ ~ne~ ~y_i~). Σημειώστε ότι υπάρχει το πολύ ένα μονοπάτι μεταξύ κάθε ζεύγους τοποθεσιών και ότι ~w_i~ = ~1~ ή ⌈~N~/~3~⌉ ~\le~ ~w_i~ ~\le~ ~N~.

Βαθμολογία

Για ~1~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~6~ και ~M~ ~\le~ ~10~.

Για επιπλέον ~2~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~20~ και ~M~ ~\le~ ~40~.

Για επιπλέον ~2~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~5\,000~, ~M~ ~\le~ ~10\,000~ και είτε ~w_i~ = ~1~ ή ⌈~N~/~2~⌉ ~\le~ ~w_i~ ~\le~ ~N~.

Για επιπλέον ~6~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~100~ και ~M~ ~\le~ ~200~.

Για επιπλέον ~2~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~500~ και ~M~ ~\le~ ~1\,000~.

Για επιπλέον ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~5\,000~ και ~M~ ~\le~ ~10\,000~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~80\,000~ και ~M~ ~\le~ ~160\,000~.

Έξοδος

Εκτυπώστε έναν ακέραιο, ο οποίος είναι το ελάχιστο άθροισμα των βαθμών δυσκολίας από όλα τα μονοπάτια που διασχίστηκαν για να επισκεφθεί κάθε τοποθεσία τουλάχιστον μια φορά.

Παράδειγμα

input

9 10
0 1 1
0 2 1
0 3 1
1 4 1
2 5 1
2 6 1
3 7 1
3 8 1
2 4 5
6 7 3

output

11

Επεξήγηση του παραδείγματος

Αυτό είναι το σύνολο των επίπεδων μονοπατιών:

Αυτό είναι όλο το σύνολο των μονοπατιών με όλα τα επίπεδα δυσκολίας

Αυτό είναι όλο το σύνολο των μονοπατιών, με όλα τα μονοπάτια με επίπεδο δυσκολίας ~1~ να έχουν παραληφθεί.

Ένας βέλτιστος περίπατος για αυτό το σύνολο μονοπατιών είναι ~4~ → ~1~ → ~0~ → ~2~ → ~5~ → ~2~ → ~6~ → ~7~ → ~3~ → ~8~ με ένα σύνολο κόστους ~1 + 1 + 1 + 1 + 1 + 1 + 3 + 1 + 1 = 11~. Δεν υπάρχει κάποιος τρόπος για να γίνει ένας περίπατος που θα επισκέπτεται όλες τις τοποθεσίες τουλάχιστον μία φορά με μικρότερο κόστος επιπέδων δυσκολίας.