Autobus

Σε μια χώρα υπάρχουν ~n~ πόλεις. Οι πόλεις συνδέονται με ~m~ δρομολόγια λεωφορείων, όπου η ~i~-οστή διαδρομή ξεκινά από την πόλη ~a_i~, καταλήγει στην πόλη ~b_i~ και διαρκεί ~t_i~ λεπτά.

Η Ema λατρεύει τα ταξίδια, αλλά δεν της αρέσει η μετεπιβίβαση μεταξύ λεωφορείων. Στο ταξίδι της θέλει να χρησιμοποιήσει το πολύ ~k~ διαφορετικά δρομολόγια λεωφορείων.

Βοηθήστε την να απαντήσει ~q~ ερωτήσεις του τύπου "Ποιος είναι ο συντομότερος χρόνος ταξιδιού για να πάω από την πόλη ~c_j~ στην πόλη ~d_j~ (χρησιμοποιώντας το πολύ ~k~ διαφορετικά δρομολόγια λεωφορείων);".

Είσοδος

Η πρώτη γραμμή περιέχει δύο θετικούς ακέραιους ~n~ και ~m\;(2 \le n \le 70,\;1 \le m \le 10^6)~, τον αριθμό των πόλεων και τον αριθμό των δρομολογίων του λεωφορείου αντίστοιχα.

Η ~i~-οστή των επόμενων ~m~ γραμμών περιέχει θετικούς ακέραιους ~a_i,\;b_i~ και ~t_i\;(1 \le a_i, b_i \le n,\;1 \le t_i \le 10^6)~, τις τερματικές πόλεις και τον χρόνο ταξιδιού της ~i~-οστής διαδρομής λεωφορείου αντίστοιχα.

Η επόμενη γραμμή περιέχει δύο θετικούς ακέραιους ~k~ και ~q\;(1 \le k \le 10^9,\;1 \le q \le n^2)~, τον μέγιστο αριθμό χρησιμοποιούμενων διαδρομών και τον αριθμό των ερωτημάτων αντίστοιχα.

Η ~j~-οστή των επόμενων ~q~ γραμμών περιέχει θετικούς ακέραιους ~c_j~ και ~d_j\;(1 \le c_j,\;d_j \le n)~, τις πόλεις από το ~j~-οστό ερώτημα.

Έξοδος

Εκτυπώστε ~q~ γραμμές. Στη ~j~-οστή γραμμή εκτυπώστε τον συντομότερο χρόνο ταξιδιού από το ~j~-οστό ερώτημα ή -1 εάν δεν υπάρχει ταξίδι που ικανοποιεί τις απαιτήσεις.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~k \le n \le 7~
2	15	~k \le 3~
3	25	~k \le n~
4	15	Κανένας επιπλέον περιορισμός.

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

input

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3

output

10
-1
0

input

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
2 3
1 4
4 2
3 3

output

6
4
0

input

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
3 3
1 4
4 2
3 3

output

3
4
0

Επεξήγηση των παραδειγμάτων:

Η απάντηση στο πρώτο ερώτημα από κάθε παράδειγμα σημειώνεται στο γράφημα.