PROGRAMING PROBLEMS

Нэгэн улсын засгийн газраас дэд бүтэцдээ эрс шинэчлэлт хийхээр болов. Тэр улс N хоттой ба тэдгээрийн K нь чухал хот ба бусад нь энгийн хот юм. Одоогоор зарим хотуудын хооронд тодорхой урттай хоёр чиглэлт зам байгаа ба ямар ч хоёр хотоос нэгээс нь нөөөд очих боломжтойгоор (өөр хотуудыг дайрч болно) бүтээгдсэн. Тэдгээр замуудаа хуучин зам гэж нэрлэдэг.
 
Засгийн газрын шинэчлэлийн хөтөлбөрийн хүрээнд
●     Бүх хуучин замуудыг нураах
●     Шинэ зам барих ажлуудыг гүйцэтгэхээр төлөвлөж байгаа.
 
Шинэ зам барихдаа дараах дүрмийг баримтлахаар шийдсэн.
●     Шинэ зам барихдаа хуучин зам байсан газраар л барьж болно. Бүх хуучин зам байсан газар шинэ зам барих албагүй.
●     Ямар ч энгийн хотоос ямар нэгэн чухал хотод очих зам олддог байх. (өөр хотуудыг дайрч болно)
●     Ямар ч чухал хотоос өөр чухал хотод очдог зам олддоггүй байх.
 
Тэгвэл та нийт барих шинэ замын уртуудын нийлбэрийн боломжит хамгийн бага утгыг олно уу.
 
Оролт
Оролтын эхний мөрөнд нийт хотуудын тоо болох N тоо, нийт чухал хотуудын тоо болох K тоо, нийт хуучин замын тоо болох P тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Хотуудыг 1 ээс N хүртэлх натурал тоогоор дугаарлана.
Дараагийн мөрөнд чухал хотуудын дугааруудыг илэрхийлэх K ширхэг харилцан ялгаатай тоонууд байна. Утгаараа [1, N] завсар харьяалагдна.
Дараагийн P мөрөнд тус бүр нь u, v, e гурван бүхэл тоо хоосон зайгаар тусгаарлагдан байрлах ба энэ нь u болон v дугаартай хотуудыг холбосон e урттай зам байгааг илэрхийлнэ.
 
Гаралт
Бодлогын хариу болох нэг ширхэг натурал тоо байна.
 
Жишээ
 
 




Жишээ оролт


Жишээ гаралт




6 2 7
1 4
1 2 1
1 3 2
2 3 1
1 4 2
4 5 1
4 6 1
5 6 2


4




6 1 6
1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 2
6 1 9


6




 
Тайлбар
1-р жишээ тестийн хувьд нийт хоёр ширхэг чухал хот байна. Дугаарууд нь 1 ба 4
Барих шинэ замууд нь
1 ба 2 дагуур хотуудыг холбосон 1 урттай зам
2 ба 3 дугаар хотуудыг холбосон 1 урттай зам
4 ба 5 дугаар хотуудыг холбосон 1 урттай зам
4 ба 6 дугаар хотуудыг холбосон 1 урттай зам барина.
 
2-р жишээ тестийн хувьд нийт нэг ширхэг чухал хот байна. Дугаар нь 1
1 ба 2 дагуур хотуудыг холбосон 1 урттай зам
2 ба 3 дугаар хотуудыг холбосон 1 урттай зам
3 ба 4 дүгээр хотуудыг холбосон 1 урттай зам
4 ба 5 дугаар хотуудыг холбосон 1 урттай зам
5 ба 6 дугаар хотуудыг холбосон 2 урттай зам барина.
 
Хялгаарлалт
Ерөнхий тестийн хувьд дараах хязгаарлалтуудад багтна.
1 <= N <= 100000
1 <= K <= N
N - 1 < P <= 200000
1 <= u, v <= N ба u != v (u нь v ээс ялгаатай)
1 <= e <= 20000
Дэд даалгаварууд
Үндсэн даалгавар нийт 4 дэд даалгаварт огтлолцолгүйгээх хуваагдна.
 
Дэд даалгавар 1
N ≤ 8 ба P ≤ 10. Энэ тохиолдолд бодвол та нийт 100 онооноос 5 оноо авна.
 
Дэд даалгавар 2
N ≤ 100 ба P ≤ 500. Энэ тохиолдолд бодвол та нийт 100 онооноос 10 оноо авна.
 
Дэд даалгавар 3
K = 1 ба нэг ширхэг чухал хоттой үед бодвол та нийт 100 онооноос 35 оноо авна.
 
Дэд даалгавар 4
Ерөнхий хязгаарлалтад бодвол өмнөх хоёр дэд даалгаварыг оруулаад нийт 100 оноо авна.