시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1323 471 329 32.639%

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 원래 모든 길마다 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

예제 입력 1

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

예제 출력 1

51
W3sicHJvYmxlbV9pZCI6IjY0OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWI4MjVcdWIwOWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzMVx1YzljNFx1Yzc3NFx1YjI5NCBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzJkY1x1YzdhNVx1Yzc3OFx1YjM3MCBcdWFjNzBcdWM5YzBcdWI3N2NcdWMxMWMgXHVjODA0XHViODI1XHViMDljXHVjNWQwIFx1YjA1OVx1YjA1OVx1YjMwNFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzZkMFx1Yjc5OCBcdWJhYThcdWI0ZTAgXHVhZTM4XHViOWM4XHViMmU0IFx1Y2YxY1x1YzgzOCBcdWM3ODhcdWIzNTggXHVhYzAwXHViODVjXHViNGYxIFx1YzkxMSBcdWM3N2NcdWJkODBcdWI5N2MgXHVjMThjXHViNGYxXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVhZTM4XHVjNzU4IFx1YWMwMFx1Yjg1Y1x1YjRmMVx1Yzc0NCBcdWNmMWMgXHViNDUwXHViYTc0IFx1ZDU1OFx1YjhlOFx1YzVkMCBcdWFlMzhcdWM3NTggXHViYmY4XHVkMTMwIFx1YzIxOFx1YjljY1x1ZDA3YyBcdWIzYzhcdWM3NzQgXHViNGU0XHVjNWI0XHVhYzAwXHViMjk0XHViMzcwLCBcdWM3N2NcdWJkODBcdWI5N2MgXHVjMThjXHViNGYxXHVkNTU4XHVjNWVjIFx1YWRmOFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWIzYzhcdWM3NDQgXHVjODA4XHVjNTdkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YjA5OCBcdWI5Y2NcdWM1N2QgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWM5ZDFcdWM3NDQgXHVjNjU1XHViNzk4XHVkNTYwIFx1YjU0YywgXHViZDg4XHVjNzc0IFx1Y2YxY1x1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWUzOFx1Yzc0NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjOWMwXHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWM3MDRcdWQ1ZDhcdWQ1NThcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWIzYzRcdWMyZGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWI0NTAgXHVjOWQxIFx1YzMwZFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM5YzQgXHVhZTM4XHViOWNjXHVjNzNjXHViODVjIFx1YzExY1x1Yjg1Y1x1Yjk3YyBcdWM2NTVcdWI3OThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNCBcdWM4NzBcdWFjNzRcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1YzgwOFx1YzU3ZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM1NjFcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1Yzc1OCBcdWMyMTggbVx1YWNmYyBcdWFlMzhcdWM3NTggXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoPGVtPjEgJmxlOyBtICZsZTsgMjAwMDAwPFwvZW0+LCA8ZW0+bS0xICZsZTsgbiAmbGU7IDIwMDAwMDxcL2VtPik8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjMTFjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWFlMzhcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNCB4LCB5LCB6XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IHhcdWJjODggXHVjOWQxXHVhY2ZjIHlcdWJjODggXHVjOWQxIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCBcdWFkZjggXHVhYzcwXHViOWFjXHVhYzAwIHpcdWJiZjhcdWQxMzBcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiAoPGVtPjAgJmxlOyB4LCB5ICZsdDsgbTxcL2VtPiwgPGVtPnggJm5lOyB5PFwvZW0+KTxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWMyZGNcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzVmMFx1YWNiMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVkNjE1XHVkMGRjXHVjNzc0XHVhY2UwKFx1Yzk4OSwgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWM5ZDFcdWM3NDQgXHVhY2U4XHViNzdjXHViM2M0IFx1YzExY1x1Yjg1YyBcdWM2NTVcdWI3OThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0KSwgXHViM2M0XHVjMmRjXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NTggXHVhYzcwXHViOWFjIFx1ZDU2OVx1Yzc0MCAyPHN1cD4zMTxcL3N1cD5cdWJiZjhcdWQxMzBcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViMDVkXHVjNWQwXHVjMTFjXHViMjk0IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgMFx1Yzc3NCAyXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWM4MDhcdWM1N2RcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NDk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGFyayByb2FkcyIsImRlc2NyaXB0aW9uIjoiXG5cbjxwPlxuRWNvbm9taWMgdGltZXMgdGhlc2UgZGF5cyBhcmUgdG91Z2gsIGV2ZW4gaW4gQnl0ZWxhbmQuIFRvIHJlZHVjZSB0aGVcbm9wZXJhdGluZyBjb3N0cywgdGhlIGdvdmVybm1lbnQgb2YgQnl0ZWxhbmQgaGFzIGRlY2lkZWQgdG8gb3B0aW1pemUgdGhlXG5yb2FkIGxpZ2h0aW5nLiBUaWxsIG5vdyBldmVyeSByb2FkIHdhcyBpbGx1bWluYXRlZCBhbGwgbmlnaHQgbG9uZyxcbndoaWNoIGNvc3RzIDEgQnl0ZWxhbmRpYW4gRG9sbGFyIHBlciBtZXRlciBhbmQgZGF5LiBUbyBzYXZlIG1vbmV5LFxudGhleSBkZWNpZGVkIHRvIG5vIGxvbmdlciBpbGx1bWluYXRlIGV2ZXJ5IHJvYWQsIGJ1dCB0byBzd2l0Y2ggb2ZmIHRoZVxucm9hZCBsaWdodGluZyBvZiBzb21lIHN0cmVldHMuIFRvIG1ha2Ugc3VyZSB0aGF0IHRoZSBpbmhhYml0YW50cyBvZlxuQnl0ZWxhbmQgc3RpbGwgZmVlbCBzYWZlLCB0aGV5IHdhbnQgdG8gb3B0aW1pemUgdGhlIGxpZ2h0aW5nIGluIHN1Y2hcbmEgd2F5LCB0aGF0IGFmdGVyIGRhcmtlbmluZyBzb21lIHN0cmVldHMgYXQgbmlnaHQsIHRoZXJlIHdpbGwgc3RpbGwgYmVcbmF0IGxlYXN0IG9uZSBpbGx1bWluYXRlZCBwYXRoIGZyb20gZXZlcnkganVuY3Rpb24gaW4gQnl0ZWxhbmQgdG8gZXZlcnlcbm90aGVyIGp1bmN0aW9uLlxuPFwvcD5cbjxwPlxuV2hhdCBpcyB0aGUgbWF4aW11bSBkYWlseSBhbW91bnQgb2YgbW9uZXkgdGhlIGdvdmVybm1lbnQgb2YgQnl0ZWxhbmRcbmNhbiBzYXZlLCB3aXRob3V0IG1ha2luZyB0aGVpciBpbmhhYml0YW50cyBmZWVsIHVuc2FmZT9cbjxcL3A+XG4iLCJpbnB1dCI6IlxuPHA+XG5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoXG50d28gbnVtYmVycyA8aT5tPFwvaT4gYW5kIDxpPm48XC9pPiwgdGhlIG51bWJlciBvZiBqdW5jdGlvbnNcbmluIEJ5dGVsYW5kIGFuZCB0aGUgbnVtYmVyIG9mIHJvYWRzIGluIEJ5dGVsYW5kLCByZXNwZWN0aXZlbHkuXG5JbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IDxpPm09bj0wPFwvaT4uIE90aGVyd2lzZSwgPGk+MSBcdTIyNjQgbVxuXHUyMjY0IDIwMDAwMDxcL2k+IGFuZCA8aT5tLTEgXHUyMjY0IG4gXHUyMjY0IDIwMDAwMDxcL2k+LiBUaGVuIGZvbGxvd1xuPGk+bjxcL2k+IGludGVnZXIgdHJpcGxlcyA8aT54LCB5LCB6PFwvaT4gc3BlY2lmeWluZyB0aGF0XG50aGVyZSB3aWxsIGJlIGEgYmlkaXJlY3Rpb25hbCByb2FkIGJldHdlZW4gPGk+eDxcL2k+IGFuZCA8aT55PFwvaT5cbndpdGggbGVuZ3RoIDxpPno8XC9pPiBtZXRlcnMgKDxpPjAgXHUyMjY0IHgsIHkgJmx0OyBtPFwvaT4gYW5kXG48aT54IFx1MjI2MCB5PFwvaT4pLiBUaGUgZ3JhcGggc3BlY2lmaWVkIGJ5IGVhY2ggdGVzdCBjYXNlIGlzIGNvbm5lY3RlZC5cblRoZSB0b3RhbCBsZW5ndGggb2YgYWxsIHJvYWRzIGluIGVhY2ggdGVzdCBjYXNlIGlzIGxlc3MgdGhhbiAyPHN1cD4zMTxcL3N1cD4uXG48XC9wPlxuIiwib3V0cHV0IjoiXG48cD5cbkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBtYXhpbXVtIGRhaWx5IGFtb3VudFxudGhlIGdvdmVybm1lbnQgY2FuIHNhdmUuXG48XC9wPlxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d