시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 118 72 61 60.396%

문제

민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다.

각 길을 통과하기 위한 비용이 각기 다르고 한 나라를 도착하면 내야할 비용 역시 나라마다 다르게 정해져있다. 민식이는 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 물론 길과 나라는 여러 번 방문할 수 있고, 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 이러한 민식이의 유럽 계획을 도와주자. 

입력

첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비용 Ci (1 ≤ Ci ≤ 1,000)가 입력된다. 다음 P개의 줄에는 P개의 길에 대한 정보를 의미하는 세 정수 Sj, Ej, Lj가 입력되는데 이는 Sj번째 나라와 Ej번째 나라 사이를 연결짓는 길을 통과하기 위해서는 Lj 비용이 든다는 의미이다. (Sj ≠ Ej, 0 ≤ Lj ≤ 1,000)

출력

첫 줄에 민식이가 유럽여행을 마치기 위한 최소비용을 출력한다.

예제 입력 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

예제 출력 1

176

힌트

민식이가 먼저 4번 나라에 도착한 다음 4-5-4-2-3-2-1-2-4 순서대로 나라를 방문하면 총 176 비용이 드는 것을 알 수 있다.

W3sicHJvYmxlbV9pZCI6IjExODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWI3ZmRcdWM1ZWNcdWQ1ODkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1YzJkZFx1Yzc3NFx1YjI5NCBcdWM1ZWNcdWI5ODRcdWM1ZDAgXHVjNzIwXHViN2ZkXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YjVhMFx1YjBhMCBcdWFjYzRcdWQ2OGRcdWM3NzRcdWIyZTQuIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWIwOThcdWI3N2NcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHVjNzc0XHVhY2UwIFx1ZDNiOFx1YjlhY1x1ZDU1OFx1YWM4YyAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViOTdjIFx1YmQ5OVx1YzYwMFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCBcdWIwOThcdWI3N2NcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc3NFx1YjNkOSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhZTM4XHVjNzQwIE1cdWFjMWNcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwIFx1YmJmY1x1YzJkZFx1Yzc3NFx1YjI5NCBcdWFkYzBcdWNjMmVcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIE5cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhYzgzXHVjNzQ0IFx1YzcyMFx1YzljMFx1YzJkY1x1ZDBhNFx1YmE3NFx1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YWUzOFx1Yzc0NCBcdWM5YzBcdWIzYzRcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBOLTFcdWFjMWNcdWM3NTggXHVhZTM4XHViOWNjXHVjNzQ0IFx1YjBhOFx1YWNhOFx1YzU3Y1x1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFlMzhcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWJlNDRcdWM2YTlcdWM3NzQgXHVhYzAxXHVhZTMwIFx1YjJlNFx1Yjk3NFx1YWNlMCBcdWQ1NWMgXHViMDk4XHViNzdjXHViOTdjIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3NCBcdWIwYjRcdWM1N2NcdWQ1NjAgXHViZTQ0XHVjNmE5IFx1YzVlZFx1YzJkYyBcdWIwOThcdWI3N2NcdWI5YzhcdWIyZTQgXHViMmU0XHViOTc0XHVhYzhjIFx1YzgxNVx1ZDU3NFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHViYmZjXHVjMmRkXHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjZDVjXHVjMThjIFx1ZDU1Y1x1YmM4OCBcdWM3NzRcdWMwYzEgXHViYzI5XHViYjM4XHVkNTU4XHViYTc0XHVjMTFjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NzQgXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNjM2VcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWJiM2NcdWI4NjAgXHVhZTM4XHVhY2ZjIFx1YjA5OFx1Yjc3Y1x1YjI5NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWNjYWIgXHVjMmRjXHVjNzkxIFx1YjA5OFx1Yjc3Y1x1YjI5NCBcdWJiZmNcdWMyZGRcdWM3NzRcdWFjMDAgXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOSBcdWIwOThcdWI3N2NcdWIyOTQgXHVjMmRjXHVjNzkxIFx1YjA5OFx1Yjc3Y1x1Yzc3NFx1YzViNFx1YzU3YyZuYnNwO1x1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmJmY1x1YzJkZFx1Yzc3NFx1Yzc1OCBcdWM3MjBcdWI3ZmQgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzI5XHViYjM4XHVkNTYwIFx1YjA5OFx1Yjc3Y1x1Yzc1OCBcdWMyMTggTig1ICZsZTsgTiAmbGU7IDEwLDAwMClcdWFjZmMgXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1YjRlNCBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWUzOFx1Yzc1OCBcdWMyMTggUChOLTEgJmxlOyBQICZsZTsgMTAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIGkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWIwOThcdWI3N2NcdWI5N2MgXHViYzI5XHViYjM4XHVkNTYwIFx1YjU0YyBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5IEM8c3ViPmk8XC9zdWI+Jm5ic3A7KDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwKVx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBQXHVhYzFjXHVjNzU4IFx1YWUzOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IFM8c3ViPmo8XC9zdWI+LCBFPHN1Yj5qPFwvc3ViPiwgTDxzdWI+ajxcL3N1Yj5cdWFjMDAgXHVjNzg1XHViODI1XHViNDE4XHViMjk0XHViMzcwIFx1Yzc3NFx1YjI5NCBTPHN1Yj5qPFwvc3ViPlx1YmM4OFx1YzlmOCBcdWIwOThcdWI3N2NcdWM2NDAgRTxzdWI+ajxcL3N1Yj5cdWJjODhcdWM5ZjggXHViMDk4XHViNzdjIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWM5ZDNcdWIyOTQgXHVhZTM4XHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgTDxzdWI+ajxcL3N1Yj4gXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjRlMFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIChTPHN1Yj5qPFwvc3ViPiAmbmU7IEU8c3ViPmo8XC9zdWI+LCAwICZsZTsgTDxzdWI+ajxcL3N1Yj4gJmxlOyAxLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YmJmY1x1YzJkZFx1Yzc3NFx1YWMwMCBcdWM3MjBcdWI3ZmRcdWM1ZWNcdWQ1ODlcdWM3NDQgXHViOWM4XHVjZTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJiZmNcdWMyZGRcdWM3NzRcdWFjMDAgXHViYTNjXHVjODAwIDRcdWJjODggXHViMDk4XHViNzdjXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1YyBcdWIyZTRcdWM3NGMgNC01LTQtMi0zLTItMS0yLTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWJhNzQgXHVjZDFkIDE3NiBcdWJlNDRcdWM2YTlcdWM3NzQgXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaGVlcmluZyB1cCB0aGUgQ293cyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIGdyb3duIHNvIGxhenkgdGhhdCBoZSBubyBsb25nZXIgd2FudHMgdG8gY29udGludWUgbWFpbnRhaW5pbmcgdGhlIGNvdyBwYXRocyB0aGF0IGN1cnJlbnRseSBwcm92aWRlIGEgd2F5IHRvIHZpc2l0IGVhY2ggb2YgaGlzIE4gKDUgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIHBhc3R1cmVzIChjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTikuIEVhY2ggYW5kIGV2ZXJ5IHBhc3R1cmUgaXMgaG9tZSB0byBvbmUgY293LiBGSiBwbGFucyB0byByZW1vdmUgYXMgbWFueSBvZiB0aGUgUCAoTi0xICZsdDs9IFAgJmx0Oz0gMTAwLDAwMCkgcGF0aHMgYXMgcG9zc2libGUgd2hpbGUga2VlcGluZyB0aGUgcGFzdHVyZXMgY29ubmVjdGVkLiBZb3UgbXVzdCBkZXRlcm1pbmUgd2hpY2ggTi0xIHBhdGhzIHRvIGtlZXAuPFwvcD5cclxuXHJcbjxwPkJpZGlyZWN0aW9uYWwgcGF0aCBqIGNvbm5lY3RzIHBhc3R1cmVzIFNfaiBhbmQgRV9qICgxICZsdDs9IFNfaiAmbHQ7PSBOOyAxICZsdDs9IEVfaiAmbHQ7PSBOOyBTX2ogIT0gRV9qKSBhbmQgcmVxdWlyZXMgTF9qICgwICZsdDs9IExfaiAmbHQ7PSAxLDAwMCkgdGltZSB0byB0cmF2ZXJzZS4gTm8gcGFpciBvZiBwYXN0dXJlcyBpcyBkaXJlY3RseSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSBwYXRoLjxcL3A+XHJcblxyXG48cD5UaGUgY293cyBhcmUgc2FkIHRoYXQgdGhlaXIgdHJhbnNwb3J0YXRpb24gc3lzdGVtIGlzIGJlaW5nIHJlZHVjZWQuIFlvdSBtdXN0IHZpc2l0IGVhY2ggY293IGF0IGxlYXN0IG9uY2UgZXZlcnkgZGF5IHRvIGNoZWVyIGhlciB1cC4gRXZlcnkgdGltZSB5b3UgdmlzaXQgcGFzdHVyZSBpIChldmVuIGlmIHlvdSYjMzk7cmUganVzdCB0cmF2ZWxpbmcgdGhyb3VnaCksIHlvdSBtdXN0IHRhbGsgdG8gdGhlIGNvdyBmb3IgdGltZSBDX2kgKDEgJmx0Oz0gQ19pICZsdDs9IDEsMDAwKS48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgc3BlbmQgZWFjaCBuaWdodCBpbiB0aGUgc2FtZSBwYXN0dXJlICh3aGljaCB5b3Ugd2lsbCBjaG9vc2UpIHVudGlsIHRoZSBjb3dzIGhhdmUgcmVjb3ZlcmVkIGZyb20gdGhlaXIgc2FkbmVzcy4gWW91IHdpbGwgZW5kIHVwIHRhbGtpbmcgdG8gdGhlIGNvdyBpbiB0aGUgc2xlZXBpbmcgcGFzdHVyZSBhdCBsZWFzdCBpbiB0aGUgbW9ybmluZyB3aGVuIHlvdSB3YWtlIHVwIGFuZCBpbiB0aGUgZXZlbmluZyBhZnRlciB5b3UgaGF2ZSByZXR1cm5lZCB0byBzbGVlcC48XC9wPlxyXG5cclxuPHA+QXNzdW1pbmcgdGhhdCBGYXJtZXIgSm9obiBmb2xsb3dzIHlvdXIgc3VnZ2VzdGlvbnMgb2Ygd2hpY2ggcGF0aHMgdG8ga2VlcCBhbmQgeW91IHBpY2sgdGhlIG9wdGltYWwgcGFzdHVyZSB0byBzbGVlcCBpbiwgZGV0ZXJtaW5lIHRoZSBtaW5pbWFsIGFtb3VudCBvZiB0aW1lIGl0IHdpbGwgdGFrZSB5b3UgdG8gdmlzaXQgZWFjaCBjb3cgYXQgbGVhc3Qgb25jZSBpbiBhIGRheS48XC9wPlxyXG5cclxuPHA+Rm9yIHlvdXIgZmlyc3QgMTAgc3VibWlzc2lvbnMsIHlvdSB3aWxsIGJlIHByb3ZpZGVkIHdpdGggdGhlIHJlc3VsdHMgb2YgcnVubmluZyB5b3VyIHByb2dyYW0gb24gYSBwYXJ0IG9mIHRoZSBhY3R1YWwgdGVzdCBkYXRhLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIFA8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXI6IENfaTxcL3A+XHJcblxyXG48cD4qIExpbmVzIE4rMi4uTitQKzE6IExpbmUgTitqKzEgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBTX2osIEVfaiwgYW5kIExfajxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCB0aGUgdG90YWwgdGltZSBpdCB0YWtlcyB0byB2aXNpdCBhbGwgdGhlIGNvd3MgKGluY2x1ZGluZyB0aGUgdHdvIHZpc2l0cyB0byB0aGUgY293IGluIHlvdXIgc2xlZXBpbmctcGFzdHVyZSk8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO November 2008 Contest > Gold 2번