Maximum Strategic Savings

Στο πολύ μακρινό παρελθόν, σε έναν γαλαξία πολύ, πολύ μακριά, υπάρχουν ~N~ πλανήτες αριθμημένοι από το ~1~ έως το ~N~. Κάθε πλανήτης έχει ~M~ πόλεις αριθμημένες από το ~1~ έως το ~M~. Έστω ότι η πόλη ~f~ του πλανήτη ~e~ συμβολίζεται ως ~(e,\;f)~.

Υπάρχουν ~N \times P~ αμφίδρομες πτήσεις στον γαλαξία. Για κάθε πλανήτη ~e\;(1 \le e \le N)~, υπάρχουν ~P~ πτήσεις αριθμημένες από το ~1~ έως το ~P~. Η πτήση ~i~ συνδέει τις πόλεις ~(e,\;a_{i})~ και ~(e,\;b_{i})~ και κοστίζει ~c_{i}~ ενέργεια ημερησίως για τη συντήρησή της.

Υπάρχουν ~M \times Q~ αμφίδρομες πύλες στον γαλαξία. Για όλες τις πόλεις με αριθμό ~f\;(1 \le f \le M)~, υπάρχουν ~Q~ πύλες αριθμημένες από το ~1~ έως το ~Q~. Η πύλη ~j~ συνδέει τις πόλεις ~(x_{j},\;f)~ και ~(y_{j},\;f)~ και κοστίζει ~z_{j}~ ενέργεια ημερησίως για τη συντήρησή της.

Είναι εφικτό να ταξιδέψει κανείς μεταξύ δύο οποιωνδήποτε πόλεων του γαλαξία χρησιμοποιώντας μόνο πτήσεις ή/και πύλες.

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

Ποιο είναι το μέγιστο ποσό ενέργειας που μπορεί να εξοικονομηθεί καθημερινά;

Είσοδος

Η πρώτη γραμμή θα περιέχει τέσσερις ακέραιους αριθμούς ~N~, ~M~, ~P~, ~Q\;(1 \le N, M, P, Q \le 10^{5})~.

Στη συνέχεια ακολουθούν ~P~ γραμμές - η ~i~-οστή θα περιέχει τρεις ακεραίους χωρισμένους με κενά διαστήματα ~a_{i}~, ~b_{i}~, ~c_{i}\;(1 \le a_{i},b_{i} \le M,\;1 \le c_{i} \le 10^{8})~.

Στη συνέχεια ακολουθούν ~Q~ γραμμές - η ~j~-οστή θα περιέχει τρεις ακέραιους αριθμούς ~x_{j}~,~\;y_{j}~, ~z_{j}\;(1 \le x_{j},y_{j} \le N,\;1 \le z_{j} \le 10^{8})~.

Είναι εγγυημένο ότι θα είναι δυνατό να ταξιδέψει κανείς μεταξύ δύο οποιωνδήποτε πόλεων χρησιμοποιώντας πτήσεις ή/και πύλες. Μπορεί να υπάρχουν πολλαπλές πτήσεις/πύλες μεταξύ του ίδιου ζεύγους πόλεων ή μια πτήση/πύλη μεταξύ μιας πόλης και του εαυτού της.

Για ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~P,\;Q \le 100~ και ~c_{i} = 1~ για όλα τα ~1 \le i \le P~, και ~z_{j} = 1~ για όλα τα ~1 \le j \le Q~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~P,\;Q \le 200~.

Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~N,\;M \le 200~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, το μέγιστο ποσό ενέργειας που μπορεί να εξοικονομηθεί καθημερινά.

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

input

2 2 1 2
1 2 1
2 1 1
2 1 1

output

3

input

2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5

output

41

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

Ένας πιθανός τρόπος είναι να καταργηθούν οι πτήσεις μεταξύ των πόλεων ~(1,\;1)~ και ~(1,\;1)~, ~(2,\;1)~ και ~(2,\;1)~, ~(1, \;1)~ και ~(1,\;2)~, ~(1,\;3)~ και ~(1,\;2)~, ~(2,\;3)~ και ~(2,\;2)~ και να καταργηθεί επίσης η πύλη μεταξύ των πόλεων ~(2,\;3)~ και ~(1,\;3)~ για συνολική εξοικονόμηση ενέργειας ~8 + 8 + 6 + 7 + 7 + 5 = 41~.