Mreža

Ο δήμαρχος της πόλης, Mirko, ζει σε μια πόλη με ~n~ γειτονιές που συνδέονται με ~n - 1~ αμφίδρομους δρόμους, έτσι ώστε από οποιαδήποτε γειτονιά είναι δυνατό να φτάσετε σε κάθε άλλη γειτονιά.

Ο Mirko θέλει να αναβαθμίσει κάποιους δρόμους για να μειώσει την κίνηση. Για κάθε δρόμο, γνωρίζουμε την τρέχουσα ταχύτητα ~v_i~ για τα οχήματα που κινούνται σε αυτόν, την τιμή της αναβάθμισης ~c_i~ και την ταχύτητα οδήγησης μετά την αναβάθμιση ~s_i~.

Υπάρχουν ~q~ δυσαρεστημένοι πολίτες που έρχονται να επισκεφτούν τον Mirko. Ο καθένας έχει την πρότασή του για αναβάθμιση. Η πρόταση του ~i~-οστού πολίτη είναι: "Να επενδύσουμε ευρώ στην αναβάθμιση των δρόμων μεταξύ των γειτονιών ~a_i~ και ~b_i~".

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

Ο Mirko σύντομα συνειδητοποίησε ότι ο υπολογισμός αυτού δεν είναι εύκολη υπόθεση και σε προσέλαβε για να τον βοηθήσεις!

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~n~ ~(1 \le n \le 100\,000)~, τον αριθμό των γειτονιών.

Σε καθεμία από τις επόμενες ~n - 1~ γραμμές υπάρχουν πέντε ακέραιοι ~x_i~, ~y_i~, ~v_i~, ~c_i~, ~s_i~ ~(1 \le x_i,\,y_i \le n,\,1 \le v_i < s_i \le 10^9,\,1\le c_i \le 10^9)~, που δηλώνουν ότι η γειτονιά ~x_i~ και ~y_i~ είναι συνδεδεμένες, η τρέχουσα ταχύτητα οδήγησης είναι ~v_i~, το κόστος αναβάθμισης του δρόμου είναι ~c_i~ και η ταχύτητα στο δρόμο θα είναι ~s_i~.

Η επόμενη γραμμή περιέχει τον ακέραιο ~q~ ~(1 \le q \le 100\,000)~, τον αριθμό των μη ικανοποιημένων πολιτών.

Σε καθεμία από τις επόμενες ~q~ γραμμές υπάρχουν τρεις ακέραιοι ~a_i~, ~b_i~, ~e_i~ ~(1 \le a_i,\,b_i \le n,\,1 \le e_i \le 10{18})~, που περιγράφουν την πρόταση του ~i~-οστού πολίτη.

Έξοδος

Στην ~i~-οστή των γραμμών ~q~ τυπώνεται η απάντηση στο αίτημα του ~i~-οστού πολίτη.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	21	~n, q \le 1\,000~
2	29	Κάθε μία από τις γειτονιές θα συνδέεται το πολύ με ~2~ άλλες γειτονιές.
3	60	Κανένας επιπλέον περιορισμός.

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

input

6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10

output

7
5
11

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

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

Αν αναβαθμίσουμε τους δρόμους μεταξύ ~1~ και ~2~ και μεταξύ ~1~ και ~3~, οι ταχύτητες οδήγησης από το ~2~ στο ~4~ θα είναι ~10~, ~9~ και ~7~ m/s. Το ελάχιστο είναι ~7~ m/s.

Αν αναβαθμίσουμε τους δρόμους μεταξύ ~4~ και ~3~, οι ταχύτητες οδήγησης από ~6~ σε ~4~ θα είναι ~5~ με ~15~ m/s. Το ελάχιστο είναι ~5~ m/s.

Αν αναβαθμίσουμε το δρόμο μεταξύ ~3~ και ~5~, η ταχύτητα οδήγησης από ~5~ σε ~3~ θα είναι ~11~ m/s.

input

4
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 10

output

6
7
5
7