C. Берландын замууд

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

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

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

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

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

Берландын засгийн газар $k$ тооны шинэ зам барихаар төлөвлөж байгаа өгөөд энэхүү баригдах замуудын урт болон ямар хотуудыг хооронд нь холбох нь мэдэгдэж байна. Шинэ замын бүтээн байгуулалтыг зөв явуулахын тулд Берландын засгийн газраас замаар холбогдох хос хотуудын хамгийн ойр зайнуудын нийлбэрийг гаргахыг хүсч байна.

Хуучин байсан болон шинээр баригдах замуудын мэдээлэл матриц хэлбэрээр өгөгджээ. Тийм бол шинэ зам баригдах бүрд хос хот бүрийн хувьд хамгийн ойрын зайнуудын нийлбэр хэд болохыг тооцоолно уу.

Оролт

Эхний мөр нь $n$ ($2 ≤ n ≤ 300$) гэсэн бүхэл тоо агуулах ба энэ нь Берландын нийт хотуудын тоог харуулна.

Дараагийн $n$ мөрүүд нь тус бүртээ $n$ гэсэн бүхэл тоо агуулах ба энэ нь хамгийн ойрын зайн матрицыг харуулна. $i$ дахь мөрний $j$ дахь бүхэл тоо $d_{i, j}$ нь $i$ болон $j$ хотуудын хоорондын хамгийн ойр зам юм. $d_{i, i} = 0, d_{i, j} = d_{j, i}$ болон өгөгдсөн матриц нь $1$-ээс $1000$ хүртэл урттай тоогоор илэрхийлэгдэх хоёр урсгалтай багц замуудын хамгийн ойр зайн матриц болно. Хот тус бүрээс дурын нэг хот руу эдгээр замуудыг ашиглан хүрэх боломжтой.

Дараагийн мөр нь $k$ ($1 ≤ k ≤ 300$) гэсэн бүхэл тоо агуулах ба энэ нь нийт төлөвлөгдсөн замуудын тоо юм. Үүний дараагийн $k$ мөрүүд нь төлөвлөгдсөн замуудын тодорхойлолтыг агуулна. Зам тус бүр нь өөр хоорондоо зайгаар тусгаарлагдах $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, 1 ≤ c_{i} ≤ 1000$) гурван бүхэл тоо агуулах ба $a_{i}$ болон $b_{i}$ нь нэг замаар холбогдох хоёр хотыг харуулах бол $c_{i}$ нь замын уртыг илэрхийлнэ. Хоёр хот хоорондоо хэдэн хэдэн замаар холбогдож болох ч тухай хотыг өөртэй нь холбодог зам байхгүй.

Гаралт

Зайгаар тусгаарлагдсан $k$ ширхэг бүхэл тоо $q_{i}$-г ($1 ≤ i ≤ k$) хэвлэнэ үү. $q_{i}$-нь 1-ээс $i$ хүртэл индекстэй замууд тавигдсаны дараах нэг замаар холбогдсон бүх хоёр хос хотуудын хоорондох хамгийн ойр зайнуудын хийлбэртэй тэнцүү байна. Замууд нь оролтод өгөгдсөн дарааллаараа $1$-ээс эхлэн дугаарлагдана. Нийлбэрийг тооцохдоо хоёр хос хот тус бүрийг яг нэг удаа авч үзэхийг анхаарна уу. Өөрөөр хэлбэл хос хотуудын дугаарыг сэлгэхгүй гэж үзнэ.

Орчуулсан: Энхгэрэл, gmunkhbaatarmn

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

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