Shop and Ship

Στη Doubleclickland, υπάρχουν ~N~ πόλεις ~(N \le 5000)~, όπου κάθε πόλη έχει διάφορους εμπορικούς δρόμους που τη συνδέουν με άλλες πόλεις. Υπάρχουν συνολικά ~T~ εμπορικοί δρόμοι ~(0 \le T \le 25\;000\;000)~ στη Doubleclickland. Για κάθε εμπορικό δρόμο μεταξύ δύο πόλεων ~x~ και ~y~, υπάρχει ένα κόστος μεταφοράς ~C(x, y)~ για τις αποστολές μεταξύ των πόλεων αυτών, όπου ~C(x, y) \ge 0~, ~C(x, y) \le 10\;000~ και ~C(x, y) = C(y, x)~. Από τις ~N~ πόλεις, ~K\;(1 \le K \le N)~ από αυτές έχουν καταστήματα με πολύ ωραία μολύβια που μπορούν να αγοραστούν διαδυκτιακά. Η τιμή για κάθε μολύβι σε μια πόλη ~x~ είναι ~P_{x}\;(0 \le P_{x} \le 10\;000)~.

Βρείτε την ελάχιστη διαδυκτιακή τιμή αγοράς ενός μολυβιού και στείλτε το σε μια συγκεκριμένη πόλη ~D\;(1 \le D \le N)~ χρησιμοποιώντας τη φθηνότερη δυνατή ακολουθία εμπορικών δρόμων. Σημειώστε ότι μπορεί να υπάρχει η δυνατότητα το μολύβι να αγοραστεί στην πόλη ~D~ και συνεπώς να μην απαιτoύνται έξοδα αποστολής.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον ~N~, τον αριθμό των πόλεων. Μπορείτε να υποθέσετε ότι οι πόλεις αριθμούνται από το ~1~ έως το ~N~. Η δεύτερη γραμμή της εισόδου θα περιέχει τον αριθμό ~T~ των εμπορικών δρόμων. Οι επόμενες ~T~ γραμμές θα περιέχουν ~3~ ακέραιους αριθμούς η καθεμιά, ~x\;y\;C(x, y)~, που δηλώνουν ότι το κόστος χρήσης του εμπορικού δρόμου μεταξύ των πόλεων ~x~ και ~y~ είναι ~C(x, y)~. Η επόμενη γραμμή θα περιέχει τον ακέραιο αριθμό ~K~ των πόλεων που διαθέτουν κάποιο κατάστημα που πουλάει διαδικτυακά αυτά τα πολύ ωραία μολύβια. Οι επόμενες ~K~ γραμμές θα περιέχουν δύο ακέραιους αριθμούς η καθεμιά, ~z~ και ~P_{z}~, που δηλώνουν ότι το κόστος ενός μολυβιού στην πόλη ~z~ είναι ~P_{z}~. Η τελευταία γραμμή περιέχει τον ακέραιο ~D~, την πόλη προορισμού.

Έξοδος

Εξάγετε το ελάχιστο συνολικό κόστος διαδυκτιακής αγοράς και αποστολής ενός τέτοιου μολυβιού στην πόλη ~D~.

Παράδειγμα

input

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

output

6