Minimum Cost Roads

Ως νεοεκλεγείσα δήμαρχος του Kitchener, η πρώτη δουλειά της Alanna είναι να βελτιώσει το οδικό δίκτυο της πόλης.

Το σημερινό οδικό σχέδιο της Kitchener μπορεί να αναπαρασταθεί ως μια συλλογή από ~N~ διασταυρώσεις με ~M~ δρόμους, όπου ο ~i~-οστός δρόμος έχει μήκος ~l_{i}~ μέτρα, κοστίζει ~c_{i}~ δολάρια ετησίως για τη συντήρησή του, και συνδέει τις διασταυρώσεις ~u_{i}~ και ~v_{i}~. Για να δημιουργήσει ένα σχέδιο, η Alanna πρέπει να επιλέξει κάποιο υποσύνολο των ~M~ δρόμων που θα διατηρήσει και θα συντηρήσει, και το κόστος αυτού του σχεδίου είναι το άθροισμα του κόστους συντήρησης όλων των δρόμων σε αυτό το υποσύνολο.

Για να μειώσει τις ετήσιες δαπάνες της πόλης, η Alanna θα ήθελε να ελαχιστοποιήσει το κόστος του σχεδίου. Ωστόσο, η πόλη απαιτεί επίσης να ελαχιστοποιήσει τις αποστάσεις των διαδρομών μεταξύ των διασταυρώσεων και θα απορρίψει κάθε σχέδιο που δεν συμμορφώνεται με αυτούς τους κανόνες. Τυπικά, για κάθε ζεύγος διασταυρώσεων ~(i,\;j)~, αν υπάρχει διαδρομή από το ~i~ στο ~j~ που έχει μήκος ~l~ μέτρα στο υπάρχον οδικό σχέδιο, το σχέδιο της Alanna πρέπει επίσης να περιλαμβάνει μια διαδρομή μεταξύ αυτών των διασταυρώσεων που είναι να το πολύ ~l~ μέτρα.

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους αριθμούς ~N~ και ~M~. Κάθε μία από τις επόμενες ~M~ γραμμές θα περιέχει τους ακέραιους αριθμούς ~u_{i}~, ~v_{i}~, ~l_{i}~ και ~c_{i}~, που σημαίνει ότι επί του παρόντος υπάρχει δρόμος από τη διασταύρωση ~u_{i}~ στη διασταύρωση ~v_{i}~ με μήκος ~l_{i}~ και κόστος ~c_{i}\;(1 \le u_{i},v_{i} \le N,\;u_{i} \neq v_{i})~.

Για ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 2000~, ~1 \le M \le 2000~, ~l_{i} = 0~ και ~1 \le c_{i} \le 10^{9}~.

Για επιπλέον ~6~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 2000~, ~1 \le M \le 2000~, ~1 \le l_{i} \le 10^{9}~, ~1 \le c_{i} \le 10^{9}~ και υπάρχει το πολύ ένας δρόμος μεταξύ οποιουδήποτε μη διατεταγμένου ζεύγους διασταυρώσεων.

Για επιπλέον ~6~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 2000~, ~1 \le M \le 2000~, ~1 \le l_{i} \le 10^{9}~ και ~1 \le c_{i} \le 10^{9}~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, το ελάχιστο δυνατό κόστος ενός οδικού σχεδίου που ανταποκρίνεται στις απαιτήσεις.

Παράδειγμα

input

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

output

25

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

Ακολουθεί ένα διάγραμμα των διασταυρώσεων μαζί με ένα έγκυρο οδικό σχέδιο με ελάχιστο κόστος.

Κάθε ακμή επισημαίνεται με ένα ζεύγος ~(l,\;c)~ που δηλώνει ότι έχει μήκος ~l~ μέτρα και κόστος ~c~ δολάρια. Επιπλέον, οι δρόμοι που αποτελούν μέρος του σχεδίου επισημαίνονται με μπλε χρώμα, με συνολικό κόστος ~7 + 1 + 6 + 7 + 4 = 25~. Μπορεί να αποδειχθεί ότι δεν μπορούμε να δημιουργήσουμε ένα φθηνότερο σχέδιο που να σέβεται επίσης τις απαιτήσεις της πόλης.