B. Жууху ба хотууд

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

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

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

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

Жууху бол А улсын ерөнхийлөгч. Тус улс нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хоттой. А улсын нийслэл нь $1$-р хот юм. Мөн хотуудыг холбосон $m$ ширхэг зам байдаг. Чи $u_i$ хотоос $v_i$ хотруу, эсрэгээрээ $v_i$ хотоос $u_i$ хотруу $i$-р замаар явж чадах ба энэ замын урт нь $x_i$ байна. Эцэст нь А улс $k$ ширхэг галт тэрэгний замтай. $i$-р галт тэрэгний замыг ашиглан нийслэлээс $s_i$ хотруу, эсрэгээр $s_i$ хотоос нийслэлрүү нэг удаа явж болдог ба замын урт нь $y_i$ байна.
Жууху улсынхаа мөнгийг үрэхийг хүсэхгүй байгаа учраас зарим галт тэрэгний замыг хаахаар болов. Дараах нөхцөлийн дагуу хамгийн ихдээ хэдэн галт тэрэгний зам хааж болохыг түүнд хэлж өгнө үү: Хот бүрээс нийслэлрүү явсан хамгийн дөт замыг өөрчилж болохгүй.

Оролт

Эхний мөрөнд гурван бүхэл тоо $n, m, k$ $(2 ≤ n ≤ 10^{5}; 1 ≤ m ≤ 3*10^{5}; 1 ≤ k ≤ 10^{5})$ байна.

Дараагийн $m$ ширхэг мөрөнд $u_i$, $v_i$, $x_i$ ($1$ ≤ $u_i$, $v_i$ ≤ $n$; $u_i$ ≠ $v_i$; $1$ ≤ $x_i$ ≤ $10^{9}$) гурван бүхэл тоо байна.

Дараагийн $k$ мөр бүрд хоёр бүхэл тоо $s_i$, $y_i$ ($2$ ≤ $s_i$ ≤ $n$; $1$ ≤ $y_i$ ≤ $10^{9}$) байна.

Дурын аль ч хотоос нийслэлрүү явах арга дор хаяж нэг байгаа. Хоёр хотын хооронд, мөн нийслэлээс аль нэг хотруу олон зам байж болохыг анхаарна уу.

Гаралт

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

Орчуулсан: Даариймаа

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

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