B. Авлига

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

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

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

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

Руританиа үнэхээр тааруухан засвар үйлчилгээ хийгддэг замын сүлжээтэй улс бөгөөд үргэлж хүргэлт хийдэг ачааны машин жолоочдод таатай мэдээ биш юм. Үнэн хэрэгтээ замууд засагдахад тэд ганцхан замтай болдог. Энэ нь заримдаа хуулийн дагуу нэг хотоос нөгөөд очих боломжгүй болж таардаг. Гэсэн хэдий ч хууль бусаар бүх хотод очиж болохыг бид мэднэ.

Аз болоход цагдаа нар авилгад автсан хандлагатай байх ба жолоочдоос бяцхан бэлэг аваад тэднийг буруу чиглэлээр явахыг зөвшөөрдөг. Зам бүр дээр нэг эргүүлийн машин байх ба жолоочоос буруу замаар явахад Руританиагийн 1000 алтан зоос хүсдэг. Гэхдээ шуналтах болсон ба тухайн замын эргүүлийн машин нэг ижил жолоочид дүрэм зөрчиж буйг сануулах бүртээ өмнөх удаад нэхсэн мөнгөнөөсөө 2 дахин ихийг нэхдэг.

Борна бол энэ хахуулийн хэв маягийг мэддэг ачааны машины жолооч. Түүний ажлын нэг хэсэг нь Руританиа даяарх зарим хотуудад $K$ удаагийн зогсолт хийх ба тодорхой захиалгын дагуу зогсдог. Руританиагийн $N$ (1-ээс $N$ хүртэл дугаарлагдсан) ширхэг хот байгаа ба Борнагийн эхлэх цэг нь нийслэл хот буюу 1-р хот. Тэр Руринатиад байгаа $N - 1$ замын гадна аль зам нь чиглэлгүй зам бэ гэдгийг мэдэх боловч цагдааг хахуулдахын тулд хэрэгтэй хамгийн бага мөнгөний хэмжээг тооцоолох боломжгүй байна. Борнад хариултыг олоход туслах юм бол танд өндөр шагнал өгнө.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $N$ байх ба Руританиад байгаа хотын тоог илэрхийлнэ. Дараагийн $N - 1$ мөрөнд хотуудын хоорондох замуудын мэдээллийг агуулна. Зам нь гурван бүхэл тоон утгууд ($a$,$b$,$x$)-аар илэрхийлэгдэх ба эдгээр нь зайгаар тусгаарлагдана. $a$ болон $b$ тоонууд нь тус замаар холбогдсон хотуудыг илтгэх ба $x$ нь 0 эсвэл 1 байна. Хэрвээ 0 байвал зам хоёр чиглэлтэй гэсэн үг харин 1 байвал зам $a -> b$ чиглэсэн хууль ёсны ганцхан урсгалтай. Дараагийн мөрөнд $K$ буюу Борнагийн зогсолтын тоо байна. Хамгийн сүүлийн мөрөнд К ширхэг эерэг бүхэл тоонууд $s_{1}, …, s_{K}$ байх ба: Борнагийн очих хотууд.

  • $1 ≤ N ≤ 10^{5}$
  • $1 ≤ K ≤ 10^{6}$
  • $1 ≤ a, b ≤ N$ бүх замын хувьд
  • бүх замын хувьд
  • $1 ≤ s_{i} ≤ N$ бүх $1 ≤ i ≤ K$-н хувьд

Гаралт

Гаралтанд ганц тоо байна: Борнагийн авилгалд зориулах хамгийн бага мөнгөний хэмжээ(хэдэн мянган Руританиагийн алтан зоос төлөх) байх ба $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

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

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

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

Тэмдэглэл

Эхлээд Борна $1 -> 5$ гэсэн замаар явах ба 1000 зоос төлнө. Дараа нь $5 -> 1 -> 2 -> 3 -> 4$ гэсэн замаар явах ба мөнгө төлөхгүй боловч буцаад $4 -> 3 -> 2 -> 1 -> 5$ замаар явахдаа 3000 (1000+2000) зоос бэлдэх хэрэгтэй. Тэгээд 2-руу $5 -> 1 -> 2$ замаар явахдаа юу ч төлөхгүй. Эцэст нь 2оос явах шаардлагагүй учир илүү мөнгө бэлдэх хэрэггүй. Иймд нийт 4000 зоос бэлдэх хэрэгтэй.

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