n хот, m зам байна. Зам бүр хоёр тийш чиглэсэн бөгөөд хоёр хотыг холбоно. Мөн k хотод анимэ дэлгүүр байдаг нь мэдэгдэж байна.
Хотод анимэ дэлгүүр байвал тэнд амьдрагч мэдээж түүнийг сайн мэднэ. Өөрийн хотод байхгүй хамгийн ойрын анимэ дэлгүүрийг олмоар байна.
Хот бүрийн хувьд анимэ дэлгүүртэй өөр хот хүртэлх хамгийн бага зайг ол.
Эхний мөрөнд n, m, k гэсэн гурван бүхэл тоо: хот, зам, анимэ дэлгүүрийн тоо. Хотууд 1,2,…,n гэж дугаарлагдсан.
Дараагийн мөрөнд k бүхэл тоо: анимэ дэлгүүртэй хотууд.
Эцэст нь m мөрөнд замууд. Мөр бүр a ба b бүхэл тоонуудыг агуулна: a болон b хотуудын хооронд зам бий.
n бүхэл тоо хэвлэ: хот бүрийн хувьд анимэ дэлгүүртэй өөр хот хүртэлх хамгийн бага зай. Ийм хот байхгүй бол оронд нь −1 хэвлэ.
9 6 4 2 4 5 7 1 2 1 3 1 8 2 4 3 4 5 6
1 1 1 1 -1 1 -1 2 -1