Janjetina

Μετά το κλείσιμο των εστιατορίων σε όλη την Κροατία λόγω του lockdown, ο κύριος Malnar στεναχωρήθηκε πολύ. Ωστόσο, σύντομα συνειδητοποίησε ότι δεν είχε νόημα να είναι λυπημένος και αποφάσισε ότι μόλις ανοίξουν ξανά τα εστιατόρια, θα ταξιδέψει σε όλη την Κροατία και θα περιποιηθεί τον εαυτό του τρώγοντας το καλύτερο αρνί που υπάρχει τα κροατικά εστιατόρια.

Ο κ. Malnar γνωρίζει n πόλεις που θα μπορούσε να επισκεφτεί, τις οποίες σημείωσε με ακέραιους αριθμούς από το 1 έως το ~n~. Επίσης, γνωρίζει για ~n - 1~ αμφίδρομους δρόμους που συνδέουν αυτές τις πόλεις, με τέτοιο τρόπο ώστε να είναι δυνατή η μετακίνηση μεταξύ δύο πόλεων.

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

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

Ο κ. Malnar θεωρεί ικανοποιητικό ένα μονοπάτι μήκους ~l~ στο οποίο τρώει ~w~ κιλά αρνιού, αν ~w - l \ge k~. Το μήκος ενός μονοπατιού είναι ίσο με τον αριθμό των δρόμων που περνάει.

Αναρωτιέται πόσα διατεταγμένα ζεύγη διακριτών πόλεων ~(x,\;y)~ υπάρχουν, έτσι ώστε το συντομότερο μονοπάτι από την πόλη ~x~ στην πόλη ~y~ να είναι ικανοποιητικό. Είναι πολύ απασχολημένος, οπότε σας ζητά να του υπολογίσετε την απάντηση.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n~ και ~k\;(1 \le n, k \le 100\,000)~, τον αριθμό των πόλεων και το "όριο ικανοποίησης".

Καθεμία από τις ακόλουθες ~n - 1~ γραμμές περιέχει τρεις ακέραιους ~x,\;y~ και ~w\;(1 \le x, y \le n, x \ne y, 1 \le w \le 100\,000)~, που σημαίνει ότι υπάρχει ένας δρόμος που συνδέει τα ~x~ και ~y~ και υπάρχει ένα εστιατόριο σε αυτόν τον δρόμο, όπου ο κύριος Malnar μπορεί να παραγγείλει ~w~ κιλά αρνί.

Έξοδος

Περιλαμβάνει τον αριθμό των διατεταγμένων ζευγών διακριτών πόλεων ~(x,\;y)~, έτσι ώστε η συντομότερη διαδρομή από την πόλη ~x~ στην πόλη ~y~ να είναι ικανοποιητική.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~1 \le n \le 1\,000~
2	35	Οι πόλεις ~i~ και ~i+1\;(1 \le i \le n-1)~ συνδέονται άμεσα.
3	60	Κανένας επιπλέον περιορισμός.

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

input

3 1
1 2 3
1 3 2

output

6

input

4 1
1 2 1
2 3 2
3 4 3

output

6

input

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

output

8

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

Τα ζευγάρια είναι ~(1, 3),\;(3, 1),\;(1, 5),\;(5, 1),\;(3, 5),\;(5, 3),\;(4, 5)~ και ~(5, 4)~.