Artskjid

Υπάρχουν πολλοί γνωστοί αλγόριθμοι για την εύρεση της συντομότερης διαδρομής από τη μια τοποθεσία στην άλλη. Οι άνθρωποι έχουν συσκευές GPS στα αυτοκίνητά τους και στα τηλέφωνά τους για να τους δείξουν τον πιο γρήγορο τρόπο για να φτάσουν εκεί που θέλουν να πάνε. Στις διακοπές, ωστόσο, στον Troy αρέσει να ταξιδεύει αργά. Θα ήθελε να πάρει τη μεγαλύτερη διαδρομή προς το δικό του προορισμός ώστε να μπορεί να επισκεφτεί πολλά νέα και ενδιαφέροντα μέρη στην πορεία.

Ως εκ τούτου, μια έγκυρη διαδρομή αποτελείται από μια ακολουθία διακριτών πόλεων ~c_1, c_2, ..., c_k~, έτσι ώστε να υπάρχει δρόμος από τη ~c_i~ στη ~c_{i+1}~ για κάθε ~1 \le i < k~.

Δεν θέλει να επισκεφτεί καμία πόλη περισσότερες από μία φορές. Μπορείτε να τον βοηθήσετε να βρει τη μεγαλύτερη διαδρομή;

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους ~n~, ~m~, τον συνολικό αριθμό των πόλεων και τον αριθμό των δρόμων που συνδέουν τις πόλεις (~2 \le n \le 18~, ~1 \le m \le n^2 - n~). Υπάρχει το πολύ ένας δρόμος από οποιαδήποτε πόλη σε οποιαδήποτε άλλη πόλη. Οι πόλεις είναι αριμθμημένες από το ~0~ έως το ~n - 1~, με το ~0~ να είναι η αρχική πόλη του Troy και ~n - 1~ ο προορισμός του.

Οι επόμενες ~m~ γραμμές της εισόδου καθεμία περιέχουν τρεις ακέραιους ~s, d, l~. Κάθε τριπλέτα υποδεικνύειότι υπάρχει ένας δρόμος μονής κατεύθυνσης από την πόλη ~s~ στην πόλη ~d~ με μήκος ~l~ km (~0 \le s \le n - 1~, ~0 \le d \le n - 1~, ~s \ne d~, ~1 \le l \le 10\,000~). Κάθε δρόμος είναι μονής κατεύθυνσης: μπορεί να πάει από το ~s~ στο ~d~, όχι το αντίθετο. Πάντα υπάρχει τουλάχιστον μία διαδρομή από την πόλη ~0~ στην πόλη ~n - 1~.

Βαθμολογία

Για τουλάχιστον 30% της βαθμολογίας για αυτό το πρόβλημα, ~n \le 8~.

Έξοδος

Εκτυπώστε έναν ακέραιο, το μήκος της μεγαλύτερης διαδρομής που ξεκινά από την πόλη ~0~, τελειώνει στην πόλη ~n - 1~ και δεν επισκέπτεται καμία πόλη πάνω από μία φορά. Το μήκος είναι το άθροισμα από τα μήκη των δρόμων που διανύονται κατά μήκος της διαδρομής.

Παράδειγμα

input

3 3
0 2 5
0 1 4
1 2 3

output

7

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

Η μικρότερη διαδρομή θα ήταν να πάρουμε τον δρόμο ευθεία από το ~0~ στο ~2~, με μήκος ~5~ km. Η διαδρομή που πάει από το ~0~ στο ~1~ και μετά στο ~2~ είναι ~4 + 3 = 7~ km, που είναι μεγαλύτερη.