E. Портал нээх

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

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

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

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

Павл компьютерийн алдартай тоглоом тоглодог. Тоглогч улсдаа өндөр хариуцлага хүлээдэг ба улс даяар чөлөөтэй аялдаг (эрэл хайгуул хийж туршлага хуримтлуулдаг).

Энэ улсад $n$ хот байдаг ба 2 чиглэлт ялгаатай урттай $m$ ширхэг замаар холбогдсон ба аль ч хотоос аль ч хотод очиж чаддаг байна. Эдгээр хотуудын $k$ нь порталтай (гэрлээр шилжүүлэгч).Тоглоом эхлэхэд бүх портал хаалттай байна. Тоглогч порталтай тааралдвал портал нээгднэ. Нээлттэй порталаар нээлттэй порталруу шилжиж болдог. Шилжихэд хугацаа өнгөрөхгүй ба энэ нь улс даяарх хотуудруу хурдан аялах боломжтой болгож байв.

Тоглоомын эхэнд Павл $1$ дүгээр хотод байна. Тэр бүх порталыг аль болох хурдан онгойлгохыг хүснэ. Хэр хугацаа хэрэгтэй вэ?

Оролт

Эхний мөрөнд $n$ and $m$ ($1 ≤ n ≤ 10^{5}$, $0 ≤ m ≤ 10^{5}$) гэсэн хот болон замын тоог илэрхийлсэн бүхэл тоо байна.

Дараагийн $m$ мөр бүрт зайгаар тусгаарлагдсан $x_{i}$, $y_{i}$, $w_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$, $x_{i} ≠ y_{i}$, $1 ≤ w_{i} ≤ 10^{9}$) бүхэл тоонууд байна, энэ нь $i$ дэх замаар холбогдсон хотуудын дугаар ба замыг дамжин өнгөрөх хугацаа. Хот бүр хамгийн ихдээ $1$ замаар холбогдно. Замуудаар дамжин аль ч хотоос аль ч хотруу очиж болдог байхаар өгөгдсөн байх болно.

Дараагийн мөрөнд $k$ ($1 ≤ k ≤ n$) гэсэн порталын тоо байна.

Дараагийн мөрөнд зайгаар тусгаарлагдсан $k$ ширхэг бүлэх тоонууд $p_{1}$, $p_{2}$, ..., $p_{k}$ байх ба эдгээр нь порталтай хотын дугаар юм. Хот бүр дээд тал нь 1 порталтай байна.

Гаралт

Бүх порталыг нээхэд зарцуулагдах хамгийн бага хугацааг ол.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Бат-Од

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

Оролт
3 3
1 2 1
1 3 1
2 3 1
3
1 2 3
Гаралт
2
Оролт
4 3
1 2 1
2 3 5
2 4 10
3
2 3 4
Гаралт
16
Оролт
4 3
1 2 1000000000
2 3 1000000000
3 4 1000000000
4
1 2 3 4
Гаралт
3000000000

Тэмдэглэл

Хоёрдахь жишээн дээр тоглогч $2$ дахь хотод ирэх ёстой ба порталыг нээх ёстой. Тэгээд $3$ дахь хотруу яван порталыг нээнэ. Тэгээд $2$ дахь хотруу порталдан $4$ дэх хотруу явж портал нээн аялалаа дуусгана.

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