B. Нарийн боовны газар

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

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

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

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

Маша $1$-ээс $n$ хүртэлх дугаарлагдсан $n$ ширхэг хотуудын аль нэгт нь өөрийн нарийн боовны газраа нээхийг хүссэн бөгөөд тухайн хотдоо жижиг талх үйлдвэрлэн зарахыг хүсжээ. Нийт $m$ ширхэг 2 урсгалтай замууд оршин байх бөгөөд эдгээр зам тус бүр нь эдгээр хотуудын аль нэг хос хотуудыг холбох ажээ.

Өөрийн нарийн боовны газраа жижиг талх үйлдвэрлэхийн тулд Маша ямар нэгэн агуулахтай гурил нийлүүлэлтийн тал дээр тохиролцох хэрэгтэй байв. Нийтдээ $k$ ширхэг агуулах оршин байх бөгөөд эдгээр нь $a_{1}, a_{2}, ..., a_{k}$ гэсэн дугаартай ялгаатай хотуудад байрлах ажээ.

Харамсалтай нь Машагийн амьдарч буй улсын хуульд зааснаар ямар нэгэн агуулах байрлаж буй хотод шинээр нарийн боовны газар нээх нь хориотой байв. Иймд тэрээр өөрийн нарийн боовны газраа эдгээр агуулахууд байрлаагүй бусад $n - k$ ширхэг хотуудад нээх бөгөөд мэдээж хэрэг гурил хүргэлтийн үйлчилгээ нь төлбөртэй байх юм. Тухайлбал Маша-ын нарийн боовны газар болон агуулахын хооронд байх хүргэлтийн маршрутын километр тутамд $1$ рубль төлөх ёстой ажээ.

Илүү тодруулбал, хэрэв Маша $b$ ($1 ≤ i ≤ k$ бүрийн хувьд $a_{i} ≠ b$ байна) гэсэн хотод өөрийн нарийн боовны газраа нээх бөгөөд $s$ ($s = a_{j}$ байх ямар нэгэн $1 ≤ j ≤ k$ оршин байна) гэсэн хотод байрлах агуулахыг гурил нийлүүлэгчээр сонгох ба $b$ болон $s$ хотууд нь хоорондоо нийт замын урт нь $x$ байх маршрутаар холбогдож байвал тэрээр $x$ рубль төлөх юм (хэрэв эдгээр хотуудын хооронд нэгээс олон тооны маршрут байвал Маша аль маршрутаар явахаа өөрөө сонгох боломжтой).

Маша их аривч бөгөөд бодлоготой хүн юм. Тэрээр өөрийн нарийн боовны газраа нээж болох хотыг олохыг хүсэж байгаа (мөн тэрээр эдгээр $k$ ширхэг агуулахуудаас нэгийг нь сонгоно. Мөн нарийн боовны газар болон агуулахын хооронд байх маршрутуудаас нэгийг сонгох юм) бөгөөд ингэхдээ тэрээр аль болох бага хэмжээний рубль гурил хүргэлтийн үйлчилгээний хөлсөнд төлөхийг хүсэж байв. Тэгвэл Маша-д туслан уг рублийн хэмжээг олж өгнө үү.

Оролт

Оролтын эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $k$ ($1 ≤ n, m ≤ 10^{5}$, $0 ≤ k ≤ n$) өгөгдөх ба эдгээр нь харгалзан Маша-ын амьдарч буй улс-дахь хотуудын тоо, эдгээр хотуудын хооронд байх замуудын тоо болон гурилын агуулахуудын тоог тус тус илэрхийлнэ.

Дараа нь $m$ ширхэг мөр өгөгдөнө. Эдгээр мөрүүдийн мөр тус болгонд нь 3 бүхэл тоо $u$, $v$ болон $l$ ($1 ≤ u, v ≤ n$, $1 ≤ l ≤ 10^{9}$, $u ≠ v$) өгөгдөх ба эдгээр нь $u$ болон $v$ гэсэн дугаартай хотуудын хооронд $l$ километр урттай зам оршин байгааг илэрхийлэх юм.

Хэрэв $k > 0$ бол оролтын сүүлийн мөрөнд $k$ ширхэг ялгаатай бүхэл тоонууд $a_{1}, a_{2}, ..., a_{k}$ ($1 ≤ a_{i} ≤ n$)-ууд өгөгдөх ба эдгээр нь гурилын агуулах байрлаж буй хотуудын дугааруудыг илэрхийлнэ. Хэрэв $k = 0$ байвал уг мөр нь оролтод өгөгдөхгүй.

Гаралт

Ганц мөрөнд Маша-ын гурил хүргэлтийн үйлчилгээний хөлсөнд төлөх ёстой боломжит хамгийн бага рублийн хэмжээг хэвлэнэ үү.

Хэрэв бодлогын нөхцөлүүдийг хангахын зэрэгцээ эдгээр $n$ ширхэг хотуудын аль нэгт нарийн боовны газрыг нээх боломжгүй байвал ганц мөрөнд "-1" гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Уг зурагт эхний жишээг дүрслэв. Агуулах байрласан хотууд болон хариултыг илэрхийлэх замыг тодруулж үзүүлэв.

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