Mice and Maze

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

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

Θα πραγματοποιήσουμε το ακόλουθο πείραμα: ένα ποντίκι τοποθετείται σε κάθε κελί του λαβύρινθου και ένα χρονόμετρο αντίστροφης μέτρησης ξεκινά. Όταν σταματήσει το χρονόμετρο, μετράμε τον αριθμό των ποντικών έξω από το λαβύρινθο.

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

Είσοδος

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

Τα κελιά του λαβύρινθου αριθμούνται ως ~1, 2, \ldots , N~ , όπου ~N~ είναι ο συνολικός αριθμός των κελιών. Μπορείτε να υποθέσετε ότι ~N \le 100~.
Οι τρεις πρώτες γραμμές εισόδου περιέχουν ~N~ , τον αριθμό των κελιών στο λαβύρινθο, ~E~, τον αριθμό του κελιού εξόδου και την αρχική τιμή ~T~ για το χρονόμετρο αντίστροφης μέτρησης (σε κάποια αυθαίρετη μονάδα χρόνου).
Η τέταρτη γραμμή περιέχει τον αριθμό ~M~ των συνδέσεων στο λαβύρινθο και ακολουθείται από ~M~ γραμμές, με καθεμία από αυτές να καθορίζει μια σύνδεση κελιών με τρεις ακέραιους αριθμούς: δύο αριθμούς κελιών ~a~ και ~b~ (στην περιοχή ~1,\ldots, N~ ) και τον αριθμό των χρονικών μονάδων που χρειάζεται ένα ποντίκι για να ταξιδέψει από το ~a~ στο ~b~.
Παρατηρήστε ότι κάθε σύνδεση είναι μονόδρομη, δηλαδή, τα ποντίκια δεν μπορούν να ταξιδέψουν από το ~b~ στο ~a~ εκτός αν υπάρχει άλλη γραμμή που προσδιορίζει αυτή τη σύνδεση. Σημειώστε επίσης ότι ο χρόνος που απαιτείται για να ταξιδέψετε προς κάθε κατεύθυνση μπορεί να είναι διαφορετικός.

Έξοδος

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

Η έξοδος αποτελείται από μία γραμμή με τον αριθμό των ποντικών που έφτασαν κελί εξόδου ~E~ το πολύ σε ~T~ μονάδες χρόνου.

Παράδειγμα

input

1
4
2
1
8
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1

outpu

3