PROGRAMING PROBLEMS

Хугацааны хязгаарлалт: 0.1 секунд
Санах ойн хязгаарлалт: 32 mb
Нэгэн компани 1-ээс n хүртэлх дугаарлагдсан n ширхэг хотуудын аль нэгэнд өөрийн ШТС  нээж бензин борлуулахыг хүсжээ. Хотуудыг хооронд нь холбосон нийт m ширхэг зам байна.
Гэтэл шатахууны нөөц агуулах байгаа хотын ШТС-ын эзэд  зөвшөөрөхгүй байв.  Яг к ширхэг хотод агуулах байгаа бөгөөд эдгээр нь ялгаатай хотуудад байрладаг.
Тиймээс агуулах байхгүй бөгөөд агуулахад хамгийн ойр хотод ШТС-аа байгуулахаар болов. Тиймээс ШТС байгуулах хотоос агуулах хүртэлх хамгийн богино зайг тооцохыг хүсэж байна. 
Оролт: Оролтын эхний мөрөнд 3 бүхэл  тоо n, m, k (1 ≤ n, m ≤ 105 ≤ n, m ≤ 105, 0 ≤ k ≤ n ≤ k ≤ n) өгөгдөх ба эдгээр нь харгалзан хотын тоо, замын тоо, агуулахын тоог илэрхийлнэ.
Дараагийн m ширхэг мөр бүрд тоо  u, v, l  (1 ≤ u, v ≤ n, 1 ≤ l ≤ 109, u ≠ v)  өгөгдөх ба эдгээр нь u болон v гэсэн дугаартай хотуудын хооронд l километр урттай зам оршин байгааг илэрхийлэх юм. Хоёр хотын хооронд хэд хэдэн зам байж болно.
Хэрэв k > 0 бол оролтын сүүлийн мөрөнд k ширхэг ялгаатай бүхэл тоо байх ба эдгээр нь агуулах байрлаж буй хотуудын дугааруудыг илэрхийлнэ. Хэрэв k = 0 байвал уг мөр нь оролтод өгөгдөхгүй.
Гаралт: ШТС байрлуулсан хотоос агуулах байрлаж буй хот хүртэлх хамгийн богино замын уртыг хэвлэнэ. Боломжгүй  бол -1 хэвлэнэ.
Хэрэв бодлогын нөхцөлүүдийг хангахын зэрэгцээ эдгээр n ширхэг хотуудын аль нэгт ШТС нээх боломжгүй байвал нэг мөрөнд "-1" гэж хэвлэнэ үү.
Жишээ:




Оролт


Гаралт


Тайлбар




5 4 2
1 2 5
1 2 3
2 3 4
1 4 10
1 5


3


1     дүгээр хот 2 дугаар хоттой 5 урттай замаар,
Мөн 1 дүгээр хот 2 дугаар   хоттой 3 урттай замаар, 
2     дугаар хот 3 дугаар хоттой 4 урттай замаар,
1 дүгээр хот 4 дүгээр хоттой   10 урттай замаар тус тус холбогдсон.
Мөн 1 ба 5 дугаар хотод   агуулах байгаа. Эндээс 2 дугаар хотод ШТС байгуулахад агуулах байгаа 1 дүгээр   хотоос хамгийн ойр буюу 3 урттай замтай байгаа.




3 1 1
1 2 3
3


-1