D. Юсландын зам

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

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

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

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

Юсланд хотын дарга саяхан сугалаанд хожсон ба хотдоо ямар нэг сайн зүйл хийж мөнгөө зарцуулахаар шийдсэн. Жишээлбэл хотын бүх замыг засах.

Юсландад хос чиглэлтэй $n - 1$ замаар холбогдсон $n$ уулзвар байдаг. Дурын уулзвараас зөвхөн эдгээр замуудыг ашиглан өөр дурын уулзварт очиж болно.

Хотод "RC company" гэх нэртэй зам засварын нэг л компани байдаг. Компаны төв нь $1$ дугаартай уулзвар дээр байрладаг. RC компани таны хэлсэн бүх замыг засахгүй. Харин тэд зарим уулзвар дээр зөвхөн тодорхой хэсэг замыг л засч чадах ажилчдаа байрлуулсан. $i$-р ажилчинд та $c_{i}$ зоос төлөх ба тэр замын $u_{i}$ уулзвараас $v_{i}$ уулзвар хүртэлх бүх хэсгийг засна.

Хотын дарга таныг Юсландын бүх замыг засах хэсэг ажилчдыг хөлслөх хамгийн хямд боломж олохыг хүсч байна. Зарим замыг хэд хэдэн удаа засч болно.

Хэрвээ бүх замыг засах боломжгүй бол $ - 1$-г хэвлэ.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 300 000$) байх ба харгалзан Юсланд дахь хотуудын тоо болон ажилчдын тоо юм.

Дараагийн $n-1$ мөр бүрт хоёр бүхэл тоон утга $x_{i}$ ба $y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$) байх ба $i$-р замаар холбогдсон уулзваруудын индекс юм.

Сүүлийн $m$ мөрөнд ажилчдын тайлбар байх ба мөр бүрт гурван бүхэл тоон утга $u_{i}$, $v_{i}$ ба $c_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $1 ≤ c_{i} ≤ 10^{9}$) байна. Энэ нь $i$-р ажилчин $v_{i}$ уулзвараас $u_{i}$ уулзвар хүртэлх бүх замыг $c_{i}$ зоосоор засна гэсэн үг. Энд $v_{i}$ нь $u_{i}$-с $1$ хооронд байна. Мөн $v_{i}$ ба $u_{i}$ нь адил байж болно.

Гаралт

Хэрвээ бүх замыг засах боломжгүй бол $ - 1$-г хэвлэ. Бусад тохиолдолд "RC company"-н ажилчдыг ашиглан бүх замыг засах хамгийн бага зардлыг илэрхийлэх нэг бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
6 5
1 2
1 3
3 4
4 5
4 6
2 1 2
3 1 4
4 1 3
5 3 1
6 3 2
Гаралт
8

Тэмдэглэл

Эхний жишээн дээр бид $1$, $3$, $4$, $5$ индекстэй ажилчдыг сонгох ёстой. Зарим замыг хэд хэдэн удаа засах боловч энэ нь зүгээр юм. Ингээд нийт өртөг нь $2 + 3 + 1 + 2 = 8$ зоостой тэнцүү.

Сэтгэгдлүүдийг ачааллаж байна...