시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 76 46 42 67.742%

문제

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

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

입력

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

출력

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

예제 입력 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 비용이 드는 것을 알 수 있다.
W3sicHJvYmxlbV9pZCI6IjExODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWI3ZmRcdWM1ZWNcdWQ1ODkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1YzJkZFx1Yzc3NFx1YjI5NCBcdWM1ZWNcdWI5ODRcdWM1ZDAgXHVjNzIwXHViN2ZkXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YjVhMFx1YjBhMCBcdWFjYzRcdWQ2OGRcdWM3NzRcdWIyZTQuIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWIwOThcdWI3N2NcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHVjNzc0XHVhY2UwIFx1ZDNiOFx1YjlhY1x1ZDU1OFx1YWM4YyAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViOTdjIFx1YmQ5OVx1YzYwMFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCBcdWIwOThcdWI3N2NcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc3NFx1YjNkOSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhZTM4XHVjNzQwIE1cdWFjMWNcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwIFx1YmJmY1x1YzJkZFx1Yzc3NFx1YjI5NCBcdWFkYzBcdWNjMmVcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIE5cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhYzgzXHVjNzQ0IFx1YzcyMFx1YzljMFx1YzJkY1x1ZDBhNFx1YmE3NFx1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YWUzOFx1Yzc0NCBcdWM5YzBcdWIzYzRcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBOLTFcdWFjMWNcdWM3NTggXHVhZTM4XHViOWNjXHVjNzQ0IFx1YjBhOFx1YWNhOFx1YzU3Y1x1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHVhYzAxIFx1YWUzOFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWFjMDFcdWFlMzAgXHViMmU0XHViOTc0XHVhY2UwIFx1ZDU1YyBcdWIwOThcdWI3N2NcdWI5N2MgXHViM2M0XHVjYzI5XHVkNTU4XHViYTc0IFx1YjBiNFx1YzU3Y1x1ZDU2MCBcdWJlNDRcdWM2YTkgXHVjNWVkXHVjMmRjIFx1YjA5OFx1Yjc3Y1x1YjljOFx1YjJlNCBcdWIyZTRcdWI5NzRcdWFjOGMgXHVjODE1XHVkNTc0XHVjODM4XHVjNzg4XHViMmU0LiBcdWJiZmNcdWMyZGRcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWNkNWNcdWMxOGMgXHVkNTVjXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWJjMjlcdWJiMzhcdWQ1NThcdWJhNzRcdWMxMWMgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWFlMzhcdWFjZmMgXHViMDk4XHViNzdjXHViMjk0IFx1YzVlY1x1YjdlYyBcdWJjODggXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Y2NhYiBcdWMyZGNcdWM3OTEgXHViMDk4XHViNzdjXHViMjk0IFx1YmJmY1x1YzJkZFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmJmY1x1YzJkZFx1Yzc3NFx1Yzc1OCBcdWM3MjBcdWI3ZmQgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHViMDk4XHViNzdjXHVjNzU4IFx1YzIxOCBOKDUgJmxlOyBOICZsZTsgMTAsMDAwKVx1YWNmYyBcdWM3NzQgXHViMDk4XHViNzdjXHViNGU0IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzIxOCBQKE4tMSAmbGU7IFAgJmxlOzEwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBpKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHViMDk4XHViNzdjXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWI1NGMgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBQXHVhYzFjXHVjNzU4IFx1YWUzOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IFNqLCBFaiwgTGpcdWFjMDAgXHVjNzg1XHViODI1XHViNDE4XHViMjk0XHViMzcwIFx1Yzc3NFx1YjI5NCBTalx1YmM4OFx1YzlmOCBcdWIwOThcdWI3N2NcdWM2NDAgRWpcdWJjODhcdWM5ZjggXHViMDk4XHViNzdjIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWM5ZDNcdWIyOTQgXHVhZTM4XHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgTGogXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjRlMFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YmJmY1x1YzJkZFx1Yzc3NFx1YWMwMCBcdWM3MjBcdWI3ZmRcdWM1ZWNcdWQ1ODlcdWM3NDQgXHViOWM4XHVjZTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6Ilx1YmJmY1x1YzJkZFx1Yzc3NFx1YWMwMCBcdWJhM2NcdWM4MDAgNFx1YmM4OCBcdWIwOThcdWI3N2NcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTVjIFx1YjJlNFx1Yzc0Y1xyXG40LTUtNC0yLTMtMi0xLTItNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHViNzdjXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YmE3NCBcdWNkMWQgMTc2IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaGVlcmluZyB1cCB0aGUgQ293cyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIGdyb3duIHNvIGxhenkgdGhhdCBoZSBubyBsb25nZXIgd2FudHMgdG8gY29udGludWUgbWFpbnRhaW5pbmcgdGhlIGNvdyBwYXRocyB0aGF0IGN1cnJlbnRseSBwcm92aWRlIGEgd2F5IHRvIHZpc2l0IGVhY2ggb2YgaGlzIE4gKDUgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIHBhc3R1cmVzIChjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTikuIEVhY2ggYW5kIGV2ZXJ5IHBhc3R1cmUgaXMgaG9tZSB0byBvbmUgY293LiBGSiBwbGFucyB0byByZW1vdmUgYXMgbWFueSBvZiB0aGUgUCAoTi0xICZsdDs9IFAgJmx0Oz0gMTAwLDAwMCkgcGF0aHMgYXMgcG9zc2libGUgd2hpbGUga2VlcGluZyB0aGUgcGFzdHVyZXMgY29ubmVjdGVkLiBZb3UgbXVzdCBkZXRlcm1pbmUgd2hpY2ggTi0xIHBhdGhzIHRvIGtlZXAuPFwvcD5cclxuXHJcbjxwPkJpZGlyZWN0aW9uYWwgcGF0aCBqIGNvbm5lY3RzIHBhc3R1cmVzIFNfaiBhbmQgRV9qICgxICZsdDs9IFNfaiAmbHQ7PSBOOyAxICZsdDs9IEVfaiAmbHQ7PSBOOyBTX2ogIT0gRV9qKSBhbmQgcmVxdWlyZXMgTF9qICgwICZsdDs9IExfaiAmbHQ7PSAxLDAwMCkgdGltZSB0byB0cmF2ZXJzZS4gTm8gcGFpciBvZiBwYXN0dXJlcyBpcyBkaXJlY3RseSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSBwYXRoLjxcL3A+XHJcblxyXG48cD5UaGUgY293cyBhcmUgc2FkIHRoYXQgdGhlaXIgdHJhbnNwb3J0YXRpb24gc3lzdGVtIGlzIGJlaW5nIHJlZHVjZWQuIFlvdSBtdXN0IHZpc2l0IGVhY2ggY293IGF0IGxlYXN0IG9uY2UgZXZlcnkgZGF5IHRvIGNoZWVyIGhlciB1cC4gRXZlcnkgdGltZSB5b3UgdmlzaXQgcGFzdHVyZSBpIChldmVuIGlmIHlvdSYjMzk7cmUganVzdCB0cmF2ZWxpbmcgdGhyb3VnaCksIHlvdSBtdXN0IHRhbGsgdG8gdGhlIGNvdyBmb3IgdGltZSBDX2kgKDEgJmx0Oz0gQ19pICZsdDs9IDEsMDAwKS48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgc3BlbmQgZWFjaCBuaWdodCBpbiB0aGUgc2FtZSBwYXN0dXJlICh3aGljaCB5b3Ugd2lsbCBjaG9vc2UpIHVudGlsIHRoZSBjb3dzIGhhdmUgcmVjb3ZlcmVkIGZyb20gdGhlaXIgc2FkbmVzcy4gWW91IHdpbGwgZW5kIHVwIHRhbGtpbmcgdG8gdGhlIGNvdyBpbiB0aGUgc2xlZXBpbmcgcGFzdHVyZSBhdCBsZWFzdCBpbiB0aGUgbW9ybmluZyB3aGVuIHlvdSB3YWtlIHVwIGFuZCBpbiB0aGUgZXZlbmluZyBhZnRlciB5b3UgaGF2ZSByZXR1cm5lZCB0byBzbGVlcC48XC9wPlxyXG5cclxuPHA+QXNzdW1pbmcgdGhhdCBGYXJtZXIgSm9obiBmb2xsb3dzIHlvdXIgc3VnZ2VzdGlvbnMgb2Ygd2hpY2ggcGF0aHMgdG8ga2VlcCBhbmQgeW91IHBpY2sgdGhlIG9wdGltYWwgcGFzdHVyZSB0byBzbGVlcCBpbiwgZGV0ZXJtaW5lIHRoZSBtaW5pbWFsIGFtb3VudCBvZiB0aW1lIGl0IHdpbGwgdGFrZSB5b3UgdG8gdmlzaXQgZWFjaCBjb3cgYXQgbGVhc3Qgb25jZSBpbiBhIGRheS48XC9wPlxyXG5cclxuPHA+Rm9yIHlvdXIgZmlyc3QgMTAgc3VibWlzc2lvbnMsIHlvdSB3aWxsIGJlIHByb3ZpZGVkIHdpdGggdGhlIHJlc3VsdHMgb2YgcnVubmluZyB5b3VyIHByb2dyYW0gb24gYSBwYXJ0IG9mIHRoZSBhY3R1YWwgdGVzdCBkYXRhLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIFA8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXI6IENfaTxcL3A+XHJcblxyXG48cD4qIExpbmVzIE4rMi4uTitQKzE6IExpbmUgTitqKzEgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBTX2osIEVfaiwgYW5kIExfajxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCB0aGUgdG90YWwgdGltZSBpdCB0YWtlcyB0byB2aXNpdCBhbGwgdGhlIGNvd3MgKGluY2x1ZGluZyB0aGUgdHdvIHZpc2l0cyB0byB0aGUgY293IGluIHlvdXIgc2xlZXBpbmctcGFzdHVyZSk8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=