ICPC Ανατολικοκεντρικός ΒΑ Τοπικός Διαγωνισμός 2016, Πρόβλημα D

Έγινε γνωστό ότι μόλις ολοκληρώσατε τη συγγραφή ενός βιβλίου με τίτλο "Πώς να εξασφαλίσετε τη νίκη σε διαγωνισμό προγραμματισμού" στα Αγγλικά, και τα αιτήματα έρχονται το ένα μετά το άλλο. Δεν αποτελεί έκπληξη το γεγονός ότι πολλά από αυτά τα αιτήματα προέρχονται από ξένες χώρες και ενώ είστε γνώστες πολλών γλωσσών προγραμματισμού, οι περισσότερες ομιλούμενες γλώσσες είναι 'κινέζικα' για εσάς. Κάνατε κάποια έρευνα και βρήκατε πολλά άτομα που μπορούν να μεταφράσουν μεταξύ των γλωσσών, αλλά με διαφορετικό κόστος. Σε ορισμένες περιπτώσεις μπορεί να χρειαστούν πολλές μεταφράσεις. Για παράδειγμα, αν δεν μπορείτε να βρείτε ένα άτομο που να μπορεί να μεταφράσει το βιβλίο σας από τα Αγγλικά στα Σουηδικά, αλλά έχετε ένα άτομο που μπορεί να μεταφράσει από τα Αγγλικά στα Γαλλικά και ένα άλλο από τα Γαλλικά στα Σουηδικά, τότε το πρόβλημα τακτοποιείται. Ενώ η ελαχιστοποίηση του συνολικού κόστους όλων αυτών των μεταφράσεων είναι σημαντική για εσάς, η πιο σημαντική προϋπόθεση είναι να ελαχιστοποιήσετε την απόσταση κάθε γλώσσας-στόχου (σε μεταφράσεις) από τα Αγγλικά, καθώς αυτό μειώνει τα σφάλματα που εμφανίζονται συνήθως κατά τη διάρκεια οποιασδήποτε μετάφρασης. Ευτυχώς, η μέθοδος για την επίλυση αυτού του προβλήματος βρίσκεται στο Κεφάλαιο 7 του νέου σας βιβλίου, επομένως δεν θα πρέπει να έχετε κανένα πρόβλημα να το λύσετε, σωστά;

Είσοδος

Η είσοδος ξεκινά με μια γραμμή που περιέχει δύο ακέραιους αριθμούς ~n~, ~m~ που υποδεικνύουν τον αριθμό των γλωσσών-στόχων και τον αριθμό των μεταφραστών που έχετε στη διάθεσή σας (~1 \le n \le 100~, ~1 \le m \le 4\, 500~). Η δεύτερη γραμμή θα περιέχει ~n~ συμβολοσειρές που καθορίζουν τις ~n~ γλώσσες-στόχους. Μετά από αυτή τη γραμμή υπάρχουν ~m~ γραμμές της μορφής ~l_1 l_2 c~ όπου οι l 1 και l 2 είναι δύο διαφορετικές γλώσσες και το ~c~ είναι ένας θετικός ακέραιος αριθμός που καθορίζει το κόστος μετάφρασης μεταξύ τους (προς κάθε κατεύθυνση). Οι γλώσσες ~l_1~ και ~l_2~ είναι πάντα είτε Αγγλικά είτε μία από τις γλώσσες-στόχους και οποιοδήποτε ζεύγος γλωσσών θα εμφανίζεται το πολύ μία φορά στην είσοδο. Το αρχικό βιβλίο είναι πάντα γραμμένο στα Αγγλικά.

Έξοδος

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

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

1ο

input

4 6
Pashto French Amheric Swedish
English Pashto 1
English French 1
English Amheric 5
Pashto Amheric 1
Amheric Swedish 5
French Swedish 1

output

8

2ο

input

2 1
A B
English B 1

output

Impossible