Minimum Cost Flow

Η πόλη Watermoo έχει κτίρια αριθμημένα με ~1~, ~2~, ~. . .~ , ~N~. Η πόλη έχει ~M~ σωλήνες που συνδέουν ζεύγη κτιρίων. Λόγω πολεοδομικών παραλείψεων, το κτίριο ~1~ είναι η μόνη μονάδα επεξεργασίας λυμάτων στην πόλη. Κάθε σωλήνας μπορεί να είναι είτε ενεργός είτε ανενεργός. Το σύνολο των ενεργών σωλήνων σχηματίζει ένα έγκυρο σχέδιο εάν το κτίριο ~1~ συνδέεται άμεσα ή έμμεσα με κάθε άλλο κτίριο μέσω ενεργών σωλήνων. (Οι σωλήνες συνδέουν τα ζεύγη κτιρίων άμεσα. Τα κτίρια ~X~ και ~Z~ συνδέονται έμμεσα, αν το ~X~ συνδέεται άμεσα ή έμμεσα με το ~Y~ και το ~Y~ συνδέεται άμεσα ή έμμεσα με το ~Z~).

Η δημοτική κυβέρνηση του Watermoo λειτουργεί επί του παρόντος ένα έγκυρο σχέδιο ~N - 1~ σωλήνων, αλλά πιστεύουν ότι είναι πολύ ακριβό! Κάθε σωλήνας έχει ένα μηνιαίο τέλος συντήρησης που πρέπει να πληρώνει ο δήμος όταν είναι ενεργός, και το συνολικό κόστος ενός έγκυρου σχεδίου είναι το άθροισμα των τελών συντήρησης των ενεργών σωλήνων του. (Οι ανενεργοί σωλήνες δεν κοστίζουν τίποτα).

Επιπλέον, οι ερευνητές του Πανεπιστημίου του Watermoo έχουν αναπτύξει ένα πειραματικό ενισχυτικό σωλήνων το οποίο μπορείτε να χρησιμοποιήσετε σε έναν σωλήνα της επιλογής σας. Θα μειώσει το κόστος αυτού του σωλήνα από ~C~ σε ~max(0,\;C - D)~, όπου ~D~ είναι η ισχύς του ενισχυτή.

Η πόλη θέλει να ελαχιστοποιήσετε το κόστος του σχεδίου και θέλει να το κάνετε γρήγορα. Κάθε μέρα, η πόλη θα σας επιτρέπει να ενεργοποιείτε έναν σωλήνα και να απενεργοποιείτε έναν άλλο. Πόσες ημέρες χρειάζεστε για να κάνετε το σύνολο των ενεργών σωλήνων να σχηματίσει ένα έγκυρο σχέδιο, του οποίου το κόστος είναι ελάχιστο μεταξύ όλων των έγκυρων σχεδίων και όλων των επιλογών ενισχυμένου σωλήνα;

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

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τους ακέραιους αριθμούς ~N~ , ~M~ και ~D\;(1 \le N \le 100\;000,\;N - 1 \le M \le 200\;000,\;0 \le D \le 10^{9})~. Κάθε μία από τις επόμενες ~M~ γραμμές θα περιέχει τρεις ακέραιους αριθμούς ~A_{i}~, ~B_{i}~ και ~C_{i}~, πράγμα που σημαίνει ότι υπάρχει ένας σωλήνας από το κτίριο ~A_{i}~ στο κτίριο ~B_{i}~ που έχει κόστος ~C_{i}~ ανά μήνα όταν ενεργοποιείται ~(1 \le A_{i},B_{i} \le N,\;1 \le C_{i} \le 10^{9})~. Οι πρώτες ~N - 1~ από αυτές τις γραμμές αντιπροσωπεύουν το έγκυρο σχέδιο που χρησιμοποιεί επί του παρόντος η πόλη.

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

Για ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 8~, ~M \le 28~ και ~D = 0~.

Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 1000~ και ~M \le 5000~ και ~D = 0~.

Για επιπλέον ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~D = 0~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 1000~ και ~M \le 5000~.

Έξοδος

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

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

input

4 4 0
1 2 1
2 3 2
3 4 1
4 1 1

output

1

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

Παρατηρήστε ότι δεν έχει σημασία σε ποιον σωλήνα χρησιμοποιείτε τον ενισχυτή σωλήνων, επειδή ~D = 0~, οπότε δεν θα επηρεάσει το τέλος συντήρησης κανενός σωλήνα. Την πρώτη ημέρα, θα πρέπει να απενεργοποιήσετε τον σωλήνα από το κτίριο ~2~ προς το ~3~ και να ενεργοποιήσετε τον σωλήνα από το κτίριο ~4~ προς το ~1~.

input

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

output

2

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

Μια λύση που χρησιμοποιεί τον ελάχιστο αριθμό ημερών είναι να χρησιμοποιηθεί πρώτα ο ενισχυτής σωλήνων στον σωλήνα από το κτίριο ~1~ προς το ~2~ για να μειωθεί το κόστος του σε ~3~. Στη συνέχεια, την πρώτη ημέρα, αντικαταστήστε τον σωλήνα από το κτίριο ~2~ προς το ~3~ με τον σωλήνα από το κτίριο ~1~ προς το ~3~ και τη δεύτερη ημέρα αντικαταστήστε τον σωλήνα από το ~1~ προς το ~4~ με τον σωλήνα από το κτίριο ~1~ προς το ~5~. Σημειώστε ότι το κόστος του βέλτιστου σχεδίου είναι ~10~. Επιπλέον, δεν υπάρχουν λύσεις όπου χρησιμοποιείτε τον ενισχυτή σωλήνων στον σωλήνα από το κτίριο ~1~ προς το ~3~ ή στον σωλήνα από το κτίριο ~1~ προς το ~5~. Κάτι τέτοιο θα έκανε τον εν λόγω σωλήνα να έχει τέλος συντήρησης ~0~, και τότε οποιοδήποτε βέλτιστο σχέδιο θα είχε κόστος ~11~ (και έχουμε ήδη δει ότι μπορούμε να επιτύχουμε κόστος ~10~).

input

4 4 0
1 2 715827882
2 3 715827882
3 4 715827882
4 1 715827884

output

0

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

Το αρχικό έγκυρο σχέδιο είναι ήδη το βέλτιστο. Προσέξτε την υπερχείλιση ακεραίων κατά την υλοποίηση της λύση σας.