The Hungary Games

Καλώς ήρθατε στους Αγώνες της Ουγγαρίας! Οι δρόμοι της Βουδαπέστης σχηματίζουν ένα στριφογυριστό δίκτυο μονόδρομων. Έχετε αναγκαστεί να συμμετάσχετε σε έναν αγώνα ως μέρος μιας εκπομπής "Reality TV" όπου τρέχετε στους δρόμους, ξεκινώντας από τα ιαματικά λουτρά Szechenyi ~s~ (για συντομία) και καταλήγοντας στον τάφο του Gul Baba (~t~για συντομία).

Φυσικά, θέλετε να ολοκληρώσετε τον αγώνα όσο το δυνατόν γρηγορότερα, γιατί θα λάβετε περισσότερη προώθητικά συμβόλαια όσο καλύτερα αποδίδετε. Ωστόσο, "κάποιο λάκο έχει η φάβα": κάθε άτομο που είναι αρκετά έξυπνο να πάρει τη συντομότερη διαδρομή ~s~-~t~ θα πεταχτεί στο σύστημα σπηλαίων Palvolgyi και θα διατηρηθεί ως εθνικός θησαυρός. Θα θέλατε να αποφύγετε αυτή τη μοίρα, αλλά να είστε όσο το δυνατόν πιο γρήγορος. Γράψτε ένα πρόγραμμα που υπολογίζει μια αυστηρά-δεύτερη-συντομότερη διαδρομή ~s~-~t~.

Μερικές φορές η αυστηρά-δεύτερη-συντομότερη διαδρομή επισκέπτεται ορισμένους κόμβους περισσότερες από μία φορές. (βλέπε την είσοδο του παραδείγματος ~2~ για παράδειγμα.)

Είσοδος

Η πρώτη γραμμή θα έχει τη μορφή ~N~ ~M~, όπου ~N~ είναι ο αριθμός των κόμβων στη Βουδαπέστη και ~M~ είναι ο αριθμός των ακμών. Οι κόμβοι είναι ~1, 2, ..., N~, ο κόμβος ~1~ αναπαριστά το ~s~ και ο κόμβος ~N~ αναπαριστά το ~t~. Έπειτα υπάρχουν ~M~ γραμμές της μορφής ~A~ ~B~ ~L~, που υποδεικνύουν έναν μονόδρομο από το ~A~ στο ~B~ μήκους ~L~. Μπορείτε να υποθέσετε ότι ~A \ne B~ σε αυτές τις γραμμές και ότι τα ταξινομημένα ζεύγη (~A, B~) είναι μοναδικά.

Έξοδος

Εκτυπώστε το μήκος μιας αυστηρά δεύτερης-συντομότερης διαδρομής από το ~s~ στο ~t~. Αν υπάρχουν λιγότερες από δύο πιθανά μήκη για τις διαδρομές από το ~s~ στο ~t~, εκτυπώστε -1.

Περιορισμοί

Κάθε μήκος ~L~ θα είναι ένας θετικός ακέραιος μεταξύ του ~1~ και του ~10\,000~. Για το 50% των περιπτώσεων δοκιμής, θα έχουμε ~2 \le N \le 40~ και ~0 \le M \le 1\,000~. Όλες οι περιπτώσεις δοκιμής θα έχουν ~2 \le N \le 20\,000~ και ~0 \le M \le 100\,000~.

Παραδείγματα

input

4 6
1 2 5
1 3 5
2 3 1
2 4 5
3 4 5
1 4 13

output

11

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

Υπάρχουν δύο συντομότερες διαδρομές μήκους ~10~ (~1 \rightarrow 2 \rightarrow 4,1 \rightarrow 3 \rightarrow4~) και η αυστηρά δεύτερη-συντομότερη διαδρομή είναι ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~ με μήκος ~11~.

input

2 2
1 2 1
2 1 1

output

3

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

Η συντομότερη διαδρομή είναι η ~1 \rightarrow 2~ μήκους ~1~ και η αυστηρά δεύτερη-συντομότερη διαδρομή είναι η ~1 \rightarrow 2 \rightarrow 1 \rightarrow 2~ μήκους ~3~.