Animal Farm

Διαχειρίζεστε μια φάρμα που έχει ~N\;(1 \le N \le 100)~ ζώα. Πήγατε στο κατάστημα και αγοράσατε ~M = N~ προκατασκευασμένους στάβλους που θα στεγάσουν τα ζώα σας. Οι στάβλοι πληρούν τις ακόλουθες συνθήκες:

• οι στάβλοι έχουν μεταξύ ~3~ και ~8~ ακμών,
• μια ακμή που καθορίζεται από δύο στάβλους συνδέει τους δύο στάβλους,
• μια ακμή που καθορίζεται μόνο μία φορά συνδέει τον συγκεκριμένο στάβλο με τον εξωτερικό χώρο,
• υπάρχει ακριβώς ένα ζώο σε κάθε στάβλο και κανένα ζώο εκτός των στάβλων, αρχικά.

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

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

Είσοδος

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

• το πρώτο στοιχείο είναι ένας ακέραιος αριθμός ~e_{p}\;(3 \le e_{p} \le 8)~, ο οποίος περιγράφει τον αριθμό των ακμών για το συγκεκριμένο στάβλο ~p~,
• το δεύτερο στοιχείο είναι μια ακολουθία ακέραιων αριθμών ~e_{p}~ που περιγράφουν τις γωνίες κάθε στάβλου, όπου κάθε ακέραιος είναι μικρότερος ή ίσος με ~1000~,
• το τρίτο στοιχείο είναι μια ακολουθία ακέραιων ~e_{p}~ που περιγράφει το κόστος κάθε ακμής, όπου κάθε ακέραιος είναι μικρότερος ή ίσος με ~5000~.

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

~3~ ~1~ ~2~ ~3~ ~7~ ~4~ ~6~

σημαίνει ότι υπάρχουν τρεις γωνίες και, συνεπώς, τρεις ακμές, όπου η ακμή ~(1,\;2)~ έχει κόστος ~7~, η ακμή ~(2,\;3)~ έχει κόστος ~4~ και η ακμή ~(3,\;1)~ έχει κόστος ~6~. Σημείωση: τουλάχιστον το ~20%~ των βαθμών αυτής της ερώτησης έχουν ~N \le 10~ και κανένας στάβλος δεν θα έχει περισσότερες από τέσσερις ακμές σε αυτά τα αρχεία ελέγχου.

Έξοδος

Σε μία γραμμή, εξάγετε το ελάχιστο κόστος που θα επιτρέψει όλα τα ζώα να συγκεντρωθούν σε ένα στάβλο ή έξω από όλους τους στάβλους.

Παράδειγμα

input

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

output

10

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

Το παρακάτω διάγραμμα εξηγεί τα δεδομένα εισόδου:

όπου οι κυκλωμένοι αριθμοί είναι οι γωνίες και οι αριθμοί με πλάγια γράμματα είναι το κόστος των ακμών. Παρατηρήστε ότι αν αφαιρεθούν οι ακμές ~(2,\;3)~, ~(4,\;5)~ και ~(4,\;7)~, όλα τα ζώα μπορούν να συναντηθούν στο στάβλο που έχει πέντε πλευρές.