Putovanje

Ο μικρός Fabijan λατρεύει τα μπαρ και τα ταξίδια. Θέλει να πιει μπύρα καφέ σε κάθε μία από τις ~N~ πόλεις της χώρας του βολικά αριθμημένα από το 1 έως το ~N~. Οι πόλεις συνδέονται μέσω ~(N - 1)~ αμφίδρομων δρόμων έτσι ώστε κάθε πόλη είναι προσβάσιμη από οποιαδήποτε άλλη πόλη διασχίζοντας κάποιους δρόμους. Ο Fabijan αποφάσισε να πιει καφέ σε κάθε πόλη με σειρά από την πόλη νούμερο 1 έως την πόλη νούμερο ~N~. Ως εκ τούτου, ξεκινά από την πόλη νούμερο 1 (όπου πίνει τον πρώτο του καφέ) και ταξιδεύει στην πόλη νούμερο 2 για τον επόμενο καφέ του. Στη διάρκεια του ταξιδιού του θα περάσει από πολλές διαφορετικές πόλεις, αλλά δεν θα κάνει μια στάση για καφέ σε αυτές. Αφού πιει καφέ στην πόλη 2, θα προχωρήσει στο ταξίδι στην πόλη 3 και ούτω καθεξής μέχρι να φτάσει τελικά στην πόλη ~N~ όπου θα πιει τον τελευταίο του καφέ.

Για να διασχίσει έναν συγκεκριμένο δρόμο, πρέπει να έχει έγκυρο εισιτήριο. Ο i-οστός δρόμος μπορεί να διασχιστεί αν έχετε είτε ένα εισιτήριο μονής εισόδου που κοστίζει ~C_{i1}~ ευρώ είτε ένα εισιτήριο πολλαπλών εισόδων που κοστίζει ~C_{i2}~ ευρώ. Σε κάθε δρόμο, ο Fabijan μπορεί να αποφασίσει να αγοράσει ένα εισιτήριο μονής εισόδου κάθε φορά που χρειάζεται να διασχίσει αυτόν τον δρόμο ή μπορεί να επιλέξει να αγοράσει ένα εισιτήριο πολλαπλών εισόδων μία φορά. Γράψτε ένα πρόγραμμα που υπολογίζει τον μικρότερο αριθμό ευρώ που χρειάζεται να ξοδέψει ο Fabijan για εισιτήρια ώστε να ολοκληρώσει με επιτυχία τα ταξίδια του.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N\;(2 \le N \le 200\,000)~.

Στην i-οστή των επόμενων ~(N - 1)~ γραμμών υπάρχουν τέσσερις ακέραιοι ~A_i,\;B_i,\;C_{i1},\;C_{i2}\;(1 \le A_i,\;B_i \le N,\;1 \le C_{i1} \le C_{i2} \le 100\,000)~ που αντιπροσωπεύουν ότι οι πόλεις ~A_i~ και ~B_i~ συνδέονται με δρόμο με τιμές εισιτηρίων ~C_{i1}~ και ~C_{i2}~.

Έξοδος

Σε μία γραμμή εξόδου το μικρότερο κόστος μετακίνησης.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~2 \le N \le 2000~
2	25	Κάθε πόλη θα συνδέεται άμεσα με δύο το πολύ άλλες πόλεις.
3	65	Κανένας επιπλέον περιορισμός.

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

input

4
1 2 3 5
1 3 2 4
2 4 1 3

output

10

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

Ο Fabijan ταξιδεύει πρώτα από την πόλη 1 στην πόλη 2 και είναι βέλτιστο γι 'αυτόν να αγοράσει ένα εισιτήριο πολλαπλών εισόδων (5 ευρώ) για το δρόμο που τους συνδέει. Στη συνέχεια ταξιδεύει από την πόλη 2 στην πόλη 3 μέσω της πόλης 1. Έχει ήδη ένα εισιτήριο πολλαπλών εισόδων που τον μεταφέρει από το 2 στο 1 και αγοράζει ένα εισιτήριο μονής εισόδου από την πόλη 1 στην πόλη 3 (2 ευρώ). Στα ταξίδια του από την πόλη 3 στην πόλη 4 αγοράζει ένα άλλο εισιτήριο μονής εισόδου που τον μεταφέρει από την πόλη 3 πίσω στην πόλη 2 (2 ευρώ) και στη συνέχεια αγοράζει ένα εισιτήριο μονής διαδρομής που τον μεταφέρει από την πόλη 2 στην πόλη 4 (1 ευρώ). Συνολικά ξόδεψε ~5 + 2 + 2 + 1 = 10~ ευρώ.

input

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

output

16

input

5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3

output

11