Problem
Caiman, şehrin garip bir bölgesinde olduğuna dair alışılmadık bir rüya görür. Bu alan, köşelerin kavşak olduğu ve kenarların bu kavşakları birbirine bağlayan iki yönlü yolların olduğu bir ağaç grafiği olarak temsil edilebilir. Toplamda n kavşak vardır ve her birinin 0'dan n-1'e kadar kendi numarası vardır.
Ama bu rüyada her şey o kadar da kötü değil, çünkü u ve v numaralı kavşaklar arasındaki her yolda C
u,v mantı var! Caiman köfteleri çok seviyor, bu yüzden olabildiğince çok yemek istiyor ama bir sorun var - herhangi bir kavşağa k defadan fazla giderse, kötü bir hamur tatlısı canavarı tarafından saldırıya uğrayacak.
Bu bir rüya olmasına rağmen, her yoldaki köfte yalnızca bir kez yenebilir, ancak hiçbir şey sizi yollarda birkaç kez yürümekten alıkoyamaz. Ayrıca Cayman yollarda durmuyor. Yani, bir kavşaktan diğerine geçmeye başlarsa, kesinlikle bir sonraki kavşağa kadar gidecektir.
Rüyanın başlangıcında, Caiman 0 numaralı yol ayrımındadır. Kötü mantı canavarı tarafından saldırıya uğramadan yiyebileceği maksimum mantı sayısını belirlemesine yardım edin.
Giriş:
İlk satır iki tamsayı içerir n ve k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; kavşak sayısı ve kavşakların her birine yapılan maksimum ziyaret sayısı.
Sonraki n - 1 satır üç tamsayı u, v ve C
u,v içerir (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub > ≤ 10000), yani u ve v numaralı kavşaklar Cu,v köfteli bir yolla birbirine bağlanır.
Kavşakların ve yolların bir ağaç oluşturması garanti edilir.
Çıktı:
Tek bir tamsayı yazdırın - Caiman'ın yiyebileceği maksimum köfte sayısı.
Örnekler:
| Giriş |
Çıktı |
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 15 |
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 17 |
11 6
1 0 7932
21 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
| 54092 |
Açıklama:
İlk örnekte, kavşakları şu sırayla ziyaret etmeniz gerekir: 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2, 7, ?2, ?8. Daha sonra toplam 1+2+2+1+3+3+3 = 15 mantı yiyecektir.
Hiçbir kavşağın 3 defadan fazla ziyaret edilmediğini unutmayın.