시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 49 22 16 40.000%

문제

사과나라에는 n 개의 도시들이 존재하며, 이 중 k 개의 도시는 국왕 구사과가 자주 방문하는 중요한 도시들이다. 또한 사과나라에는 m 개의 도시와 도시를 잇는 도로가 존재한다. 각각의 도시들은 1~n의 번호가 매겨져 있다.

어느 날 갑자기 사과나라에 폭풍이 몰아쳤다. 이 폭풍은 사과나라 건국 이래 최대 규모의 자연 재해였으며, 이 때문에 모든 도로들은 제 구실을 하지 못하게 되었다. 따라서 사과나라의 대신들은 도시들 간의 교류를 이어나가기 위해 도로들을 재건하기로 결정하였다. 이를 위해, 대신들은 각각의 도로를 재건하는 데 드는 비용을 조사하여 알아내었다.

그러나, 평소 사치와 향락에 찌든 생활을 하던 구사과 때문에 사과나라의 국고는 텅텅 비어버렸고, 이 때문에 모든 도로를 재건할 수는 없었다. 대신들은 일단 급한 대로 모든 중요한 도시가 서로 이어질 수 있도록 (즉, 각각의 중요한 도시들에서 다른 모든 중요한 도시에 도달할 수 있도록) 우선적으로 도로를 재건하고자 한다.

대신들은 세계 최고의 프로그래머인 당신에게 모든 중요한 도시가 서로 이어질 수 있도록 도로를 재건하는 최소 비용을 알아내도록 의뢰하였다. 우매한 사과나라 사람들에게 당신의 실력을 보여 주자.

입력

첫 번째 줄에는 도시의 개수 n, 중요한 도시의 개수 k, 도로의 개수 m이 공백으로 구분되어 주어진다.

두 번째 줄에는 공백으로 구분된 k개의 수들이 주어진다. 이 수들은 1 이상 n 이하의 서로 다른 정수들로, 중요한 도시들의 번호를 나타낸다.

다음 줄부터는 m개의 줄에 걸쳐 각 도로에 대한 정보가 주어진다. 각 줄에는 세 정수 a, b, c가 주어진다. 이는 이 도로가 도시 a와 도시 b를 잇고 있으며, 이 도로를 재건하는 데에 c의 비용이 소모된다는 뜻이다.

모든 도시들이 도로를 통해 연결되어 있음을 가정해도 좋다.

  • 1 ≤ c ≤ 109
  • n ≥ k
  • 2 ≤ k ≤ 5
  • n ≤ 105
  • 1 ≤ m ≤ 2 ⋅ 105

출력

당신은 모든 중요한 도시가 서로 이어질 수 있도록 도로를 재건하는 최소 비용을 하나의 정수로 출력해야 한다.

예제 입력 1

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

예제 출력 1

11
W3sicHJvYmxlbV9pZCI6IjEyNzUyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2M0XHVjMmRjXHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYWNcdWFjZmNcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgbiBcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHViNGU0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCwgXHVjNzc0IFx1YzkxMSBrIFx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWIyOTQgXHVhZDZkXHVjNjU1IFx1YWQ2Y1x1YzBhY1x1YWNmY1x1YWMwMCBcdWM3OTBcdWM4ZmMgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI0ZTRcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWMwYWNcdWFjZmNcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgbSBcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHVjNjQwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0MCAxfm5cdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjI5MCBcdWIwYTAgXHVhYzExXHVjNzkwXHVhZTMwIFx1YzBhY1x1YWNmY1x1YjA5OFx1Yjc3Y1x1YzVkMCBcdWQzZWRcdWQ0OGRcdWM3NzQgXHViYWIwXHVjNTQ0XHVjY2U0XHViMmU0LiBcdWM3NzQgXHVkM2VkXHVkNDhkXHVjNzQwIFx1YzBhY1x1YWNmY1x1YjA5OFx1Yjc3YyBcdWFjNzRcdWFkNmQgXHVjNzc0XHViNzk4IFx1Y2Q1Y1x1YjMwMCBcdWFkZGNcdWJhYThcdWM3NTggXHVjNzkwXHVjNWYwIFx1YzdhY1x1ZDU3NFx1YzYwMFx1YzczY1x1YmE3MCwgXHVjNzc0IFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViNGU0XHVjNzQwIFx1YzgxYyBcdWFkNmNcdWMyZTRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMwYWNcdWFjZmNcdWIwOThcdWI3N2NcdWM3NTggXHViMzAwXHVjMmUwXHViNGU0XHVjNzQwIFx1YjNjNFx1YzJkY1x1YjRlNCBcdWFjMDRcdWM3NTggXHVhZDUwXHViOTU4XHViOTdjIFx1Yzc3NFx1YzViNFx1YjA5OFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViM2M0XHViODVjXHViNGU0XHVjNzQ0IFx1YzdhY1x1YWM3NFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWM2MDBcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzQsIFx1YjMwMFx1YzJlMFx1YjRlNFx1Yzc0MCBcdWFjMDFcdWFjMDFcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1YzdhY1x1YWM3NFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWM4NzBcdWMwYWNcdWQ1NThcdWM1ZWMgXHVjNTRjXHVjNTQ0XHViMGI0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIwOTgsIFx1ZDNjOVx1YzE4YyBcdWMwYWNcdWNlNThcdWM2NDAgXHVkNWE1XHViNzdkXHVjNWQwIFx1Y2MwY1x1YjRlMCBcdWMwZGRcdWQ2NWNcdWM3NDQgXHVkNTU4XHViMzU4IFx1YWQ2Y1x1YzBhY1x1YWNmYyBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMGFjXHVhY2ZjXHViMDk4XHViNzdjXHVjNzU4IFx1YWQ2ZFx1YWNlMFx1YjI5NCBcdWQxNDVcdWQxNDUgXHViZTQ0XHVjNWI0XHViYzg0XHViODM4XHVhY2UwLCBcdWM3NzQgXHViNTRjXHViYjM4XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjN2FjXHVhYzc0XHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWM1YzhcdWIyZTQuIFx1YjMwMFx1YzJlMFx1YjRlNFx1Yzc0MCBcdWM3N2NcdWIyZTggXHVhZTA5XHVkNTVjIFx1YjMwMFx1Yjg1YyA8c3Ryb25nPlx1YmFhOFx1YjRlMCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViM2M0XHVjMmRjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM3NzRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCA8XC9zdHJvbmc+KFx1Yzk4OSwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI0ZTRcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkKSBcdWM2YjBcdWMxMjBcdWM4MDFcdWM3M2NcdWI4NWMgXHViM2M0XHViODVjXHViOTdjIFx1YzdhY1x1YWM3NFx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjMwMFx1YzJlMFx1YjRlNFx1Yzc0MCBcdWMxMzhcdWFjYzQgXHVjZDVjXHVhY2UwXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmEzOFx1Yzc3OCBcdWIyZjlcdWMyZTBcdWM1ZDBcdWFjOGMgPHN0cm9uZz5cdWJhYThcdWI0ZTAgXHVjOTExXHVjNjk0XHVkNTVjIFx1YjNjNFx1YzJkY1x1YWMwMCBcdWMxMWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViM2M0XHViODVjXHViOTdjIFx1YzdhY1x1YWM3NFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5PFwvc3Ryb25nPlx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIzYzRcdWI4NWQgXHVjNzU4XHViOGIwXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM2YjBcdWI5ZTRcdWQ1NWMgXHVjMGFjXHVhY2ZjXHViMDk4XHViNzdjIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWIyZjlcdWMyZTBcdWM3NTggXHVjMmU0XHViODI1XHVjNzQ0IFx1YmNmNFx1YzVlYyBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHVhYzFjXHVjMjE4IG4sIFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWM3NTggXHVhYzFjXHVjMjE4IGssIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBrXHVhYzFjXHVjNzU4IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWI0ZTRcdWM3NDAgMSBcdWM3NzRcdWMwYzEgbiBcdWM3NzRcdWQ1NThcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMyMThcdWI0ZTRcdWI4NWMsIFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMFx1YjI5NCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IGEsIGIsIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWIzYzRcdWMyZGMgYVx1YzY0MCBcdWIzYzRcdWMyZGMgYlx1Yjk3YyBcdWM3ODdcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzQgXHViM2M0XHViODVjXHViOTdjIFx1YzdhY1x1YWM3NFx1ZDU1OFx1YjI5NCBcdWIzNzBcdWM1ZDAgY1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHVjMThjXHViYWE4XHViNDFjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3NGNcdWM3NDQgXHVhYzAwXHVjODE1XHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgYyAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT5uICZnZTsgazxcL2xpPlxyXG5cdDxsaT4yICZsZTsgayAmbGU7IDU8XC9saT5cclxuXHQ8bGk+biAmbGU7IDEwPHN1cD41PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgbSAmbGU7IDIgJnNkb3Q7IDEwPHN1cD41PFwvc3VwPjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHViMmY5XHVjMmUwXHVjNzQwIDxzdHJvbmc+XHViYWE4XHViNGUwIFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjMTFjXHViODVjIFx1Yzc3NFx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM3YWNcdWFjNzRcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOTxcL3N0cm9uZz5cdWM3NDQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyNzUyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2l0aWVzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgbiBjaXRpZXMgaW4gQnl0ZWxhbmQsIGFuZCBrIG9mIHRoZW0gYXJlIGltcG9ydGFudCBjaXRpZXMgZnJlcXVlbnRseSB2aXNpdGVkIGJ5IHRoZSBraW5nIG9mIEJ5dGVsYW5kLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgYWxzbyBtIHJvYWRzIGluIHRoZSBjb3VudHJ5LCBlYWNoIG9mIHRoZW0gY29ubmVjdGluZyB0d28gY2l0aWVzLiBVbmZvcnR1bmF0ZWx5LCB0aGUgY29uZGl0aW9uIG9mIHRoZSByb2FkcyBpcyBzbyBiYWQgdGhhdCB0aGUga2luZyBjYW5ub3QgZHJpdmUgdGhyb3VnaCB0aGVtIGF0IGZ1bGwgc3BlZWQgd2l0aCBoaXMgc3BvcnRzIGNhci48XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggcm9hZCwgdGhlIGNvc3QgZm9yIHJlbm92YXRpbmcgaXQgaXMga25vd24uIFlvdXIgdGFzayBpcyB0byBjaG9vc2Ugd2hpY2ggcm9hZHMgd2lsbCBiZSByZW5vdmF0ZWQgc28gdGhhdCBhbGwgayBpbXBvcnRhbnQgY2l0aWVzIGFyZSBjb25uZWN0ZWQgd2l0aCByZW5vdmF0ZWQgcm9hZHMsIGFuZCB0aGUgdG90YWwgY29zdCBpcyBhcyBsb3cgYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgaW5wdXQgbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBuLCBrIGFuZCBtOiB0aGUgbnVtYmVyIG9mIGNpdGllcywgdGhlIG51bWJlciBvZiBpbXBvcnRhbnQgY2l0aWVzIGFuZCB0aGUgbnVtYmVyIG9mIHJvYWRzLiBUaGUgY2l0aWVzIGFyZSBudW1iZXJlZCAxLCAyLCAuLi4sIG4uIFRoZSBzZWNvbmQgaW5wdXQgbGluZSBjb250YWlucyBrIGludGVnZXJzOiB0aGUgaW1wb3J0YW50IGNpdGllcy48XC9wPlxyXG5cclxuPHA+RmluYWxseSwgdGhlIGlucHV0IGNvbnRhaW5zIG0gbGluZXMgdGhhdCBkZXNjcmliZSB0aGUgcm9hZHMuIEVhY2ggbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBhLCBiIGFuZCBjLCBtZWFuaW5nIHRoYXQgdGhlcmUgaXMgYSBiaWRpcmVjdGlvbmFsIHJvYWQgYmV0d2VlbiBjaXRpZXMgYSBhbmQgYiwgYW5kIHRoZSByZW5vdmF0aW9uIGNvc3QgZm9yIHRoZSByb2FkIGlzIGMuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgdGhlcmUgaXMgYSByb3V0ZSBiZXR3ZWVuIGFueSB0d28gY2l0aWVzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBjICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcblx0PGxpPm4gJmdlOyBrPFwvbGk+XHJcblx0PGxpPjIgJmxlOyBrICZsZTsgNTxcL2xpPlxyXG5cdDxsaT5uICZsZTsgMTA8c3VwPjU8XC9zdXA+PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBtICZsZTsgMiAmc2RvdDsgMTA8c3VwPjU8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3Ugc2hvdWxkIG91dHB1dCB0aGUgbWluaW11bSB0b3RhbCBjb3N0IGZvciByZW5vdmF0aW5nIHRoZSByb2FkcyBzbyB0aGF0IHRoZSBraW5nIGNhbiB0cmF2ZWwgYmV0d2VlbiBhbGwgaW1wb3J0YW50IGNpdGllcyB3aXRoIGhpcyBzcG9ydHMgY2FyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2016 4번

  • 문제를 번역한 사람: khsoo01