Το Έδαφος Είναι Λάβα

Έχετε παγιδευτεί σε ένα καυτό μπουντρούμι με ~N~ δωμάτια, αριθμημένα από ~1~ έως ~N~, τα οποία συνδέονται με ~M~ σήραγγες. Η ~i~-οστή σήραγγα συνδέει τα δωμάτια ~a_i~ και ~b_i~ και προς τις δύο κατευθύνσεις, αλλά το δάπεδο της σήραγγας είναι καλυμμένο με λάβα θερμοκρασίας ~c_i~.

Για βοηθηθείτε στο να διασχίζετε τις σήραγγες με λάβα, φοράτε ένα ζευγάρι θερμομονωτικές μπότες, οι οποίες αρχικά έχουν επίπεδο ψύξης ~0~. Για να πατήσετε σε λάβα θερμοκρασίας ~c~, οι μπότες σας πρέπει να έχουν ακριβώς το ίδιο επίπεδο ψύξης ~c~. Αν το επίπεδο ψύξης είναι πολύ χαμηλό, η λάβα θα λιώσει τις μπότες σας, ενώ αν είναι πολύ υψηλό, τα πόδια σας θα παγώσουν καθώς διασχίζετε τη σήραγγα.

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

Ξεκινάτε από το δωμάτιο ~1~ και θέλετε να φτάσετε στην έξοδο, η οποία γνωρίζετε ότι βρίσκεται στο δωμάτιο ~N~. Ποιο είναι το ελάχιστο κόστος για να το πετύχετε;

Είσοδος

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

Οι επόμενες ~M~ γραμμές περιέχουν τρεις ακέραιους ~a_i~, ~b_i~ και ~c_i~ (~1 \le a_i,b_i \le N~, ~a_i \ne b_i~, ~1 \le c_i \le 10^9~), οι οποίοι περιγράφουν την ~i~-οστή σήραγγα.

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

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμοι ~15~ βαθμοί:

Βαθμοί	Επιπλέον Περιορισμοί
~2~	~M=N-1~
~4~	Για όλες τις σήραγγες, ~1 \le c_i \le 10~.
~4~	Κάθε δωμάτιο έχει το πολύ ~5~ εξερχόμενες σήραγγες.
~5~	Κανένας επιπλέον περιορισμός.

Έξοδος

Εκτυπώστε το ελάχιστο κόστος, σε νομίσματα, για να φτάσετε από το δωμάτιο ~1~ στο δωμάτιο ~N~.

input

5 7
1 2 3
2 3 2
1 3 6
3 4 3
4 5 7
2 4 1
2 5 10

output

9

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

Η παραπάνω εικόνα δείχνει ένα διάγραμμα του μπουντρουμιού.

Η βέλτιστη στρατηγική διαφυγής είναι η εξής:

1. Αυξήστε το επίπεδο ψύξης στο ~3~, με κόστος ~3~ νομίσματα.
2. Διασχίστε τον διάδρομο προς το δωμάτιο ~2~.
3. Μειώστε το επίπεδο ψύξης στο ~2~, με κόστος ~1~ νόμισμα.
4. Διασχίστε τον διάδρομο προς το δωμάτιο ~3~.
5. Αυξήστε το επίπεδο ψύξης στο ~3~, με κόστος ~1~ νόμισμα.
6. Διασχίστε τον διάδρομο προς το δωμάτιο ~4~.
7. Αυξήστε το επίπεδο ψύξης στο ~7~, με κόστος ~4~ νομίσματα.
8. Διασχίστε τον διάδρομο προς το δωμάτιο ~5~ και διαφύγετε.

Το συνολικό κόστος είναι ~9~ νομίσματα και μπορεί να αποδειχθεί ότι δεν υπάρχει φθηνότερη διαδρομή.