E. Мөргөлчид

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эрт урьдын цагт Dudeland хэмээх газар байжээ. Dudeland $n-1$ ширхэг 2 чиглэлт замаар холбогдсон $n$ ширхэг тосгодоос бүрддэг. Тосгод нь $1$-с $n$ хүртэл дугаарлагдсан ба аль ч хотоос аль ч хот руу замуудаас дамжаад хүрч болдог. Dudeland-д $m$ ширхэг сүм байдаг ба эдгээр нь $m$ ширхэг ялгаатай тосгодод байрладаг. Сүм бүрд нэг мөргөлчин амьдардаг.

Жилийн эхэнд мөргөлч түүний амьдарч буй сүмээс хамгийн ойр сүмийг бичиж тэмдэглэдэг. Хэрэв нэгээс олон ширхэг хамгийн хол сүм байвал тэр бүгдийг нь л бичдэг. Шашны ариун өдөр (5 сарын 6- The Big Lebowski day) мөргөлч бүр түүний цаасан дээр тэмдэглэсэн сүмүүд байрлах тосгодын аль нэг рүү дураар алхаж эхэлдэг.

Волтер мөргөлчдөд дургүй тул тэр тэдний аль болох олонд нь тэднийг аяллаа дуусгаж чадахгүй болгох замаар таагүй сэтгэгдэл төрүүлэхийг хүсчээ. Тэр сүм агуулдаггүй яг нэг тосгоныг устгахаар төлөвлөжээ. Үүний дараагаар мөргөлчийн тэмдэглэл дээрх бүх сүм түүний хувьд хүрэх боломжгүй(түүний амьдарч байгаа тосгоноос) болчихвол тэрээр таагүй болдог.

Та Волтер хамгийн олондоо хэдэн мөргөлчид таагүй сэтгэгдэл төрүүлж чадахыг олно уу. Мөн үүнийгээ хэдэн янзаар гүйцэлдүүлж чадах тоог ч мөн олно уу. Өөрөөр хэлбэл хэдэн өөр тосгон устгавал тэр хүссэндээ хүрч болох вэ?

Оролт

Эхний мөрөнд $n (3\le n\le 10^5), m (2\le m

Дараагийн $n-1$ мөр тус бүрт $a_i, b_i, c_i, (1\le a_i,b_i\le n,1\le c_i\le 1000,a_i\not= b_i)$ энэ нь $a_i, b_i$ тосгодын хооронд $c_i$ урттай зам байгаа илтгэнэ..

Гаралт

Волтер хамгийн ихдээ хэдэн мөргөлчид таагүй сэтгэгдэл үлдээж чадах тоо болон үүнийгээ хэдэн янзаар хэрэгжүүлж чадах тоог тус тус хэвлэнэ үү.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
8 5
7 2 5 4 8
1 2 1
2 3 2
1 4 1
4 5 2
1 6 1
6 7 8
6 8 10
Гаралт
5 1
Сэтгэгдлүүдийг ачааллаж байна...