PROGRAMING PROBLEMS

Хугацааны хязгаарлалт: 3 сек
	2016 оны зун улаанбаатар хотод ACEM-ийн ээлжит нэгэн хурал зохион байгуулагдахаар болсон. Уг хурлын төлөвлөгөөнд хуралд оролцохоор ирсэн зочдыг монголын үзэсгэлэнт газруудаар аялуулах үйл ажиллагаа багтсан. Уг аялал нь улаанбаатар хотоос эхлээд товлосон К ширхэг газруудаар тойрон аялал хийж буцаад улаанбаатар хотод ирэх ёстой. Харин хурал зохион байгуулах албаныхан эдийн засгийн хямралаас болоод эдгээр газруудруу ямар дарааллаар тойрон аялавал хамгийн бага зардал гарахыг мэдэхийг хүсчээ.
 
Улаанбаатар хотын дугаар ямагт 1 байна. Мөн бүх хотууд хоорондоо холбогдсон.
Оролт:
Эхний мөрөнд монголын нийт хотын тоо N (1 < N <= 105), очихоор төлөвлөсөн газрын тоо K (0 < K < 10) болон хот хоорондын замын тоог илэрхийлэх M (1 < M < 2 * 105) өгөгдөнө. 
Хоёрдугаар мөрөнд К ширхэг товлосон хотын дугаарууд байна. 
Дараагийн N ширхэгмөр бүрт V, U, W (1 <= V, U <= N, 0 < W < 105) 3 тоо байрлана. Эдгээр нь V хотоос U хотын хоорондын хоёр чиглэлтэй замыг илэрхийлэх ба уг замаар явахад W төгрөг зарцуулна. 
 
Гаралт:
Цор ганц мөрөнд тойрон аялал хийхэд зарцуулж болох хамгийн бага зардлыг хэвлэнэ. Нэг явсан замаараа дахиж явж болно. 
 
Нийт тестийн 20%-д нь N = K байна.
Нийт тестийн 20%-д нь N > K ба N <= 500 байна.
Үлдсэн 60%-д нь үндсэн хязгаарлалтаараа байна.
 
 
Жишээ 




acem.in


acem.out


Жишээний тайлбар




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


11
 


Тайлбар: 1→5→3→6→4→5→1 гэсэн хотуудын дарааллаар явахад 4 болон 3-р   хотыг дайрсан хамгийн бага үнэлгээт зам болно.