시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB54444280.769%

문제

윤이와 달구와 포닉스는 바닥에 고정된 고리에 $N$개의 풍선과 $M$개의 실을 이어서 UDPC를 상징하는 조형물을 만들고 있다. 실을 이용하면 풍선과 풍선, 또는 풍선과 고리를 연결할 수 있다. 풍선은 자신에게 연결된 실 중 어느 하나가 팽팽해질 때까지 위로 떠오른다. 실이 꼬이거나 풍선끼리 부딪히는 경우는 없다고 가정하며, 풍선의 크기는 무시한다.

완성된 조형물을 살펴보던 포닉스는 실이 너무 많이 연결된 것 같아서 필요하지 않은 실을 잘라내기로 했다. 실을 자르고 난 뒤에는 풍선의 높이가 변하거나 풍선이 멀리 날아가 버리면 안 된다. 포닉스는 더이상 잘라낼 수 있는 실이 없을 때까지 실을 자를 것이다.

달구는 남은 실의 길이의 합이 가장 크도록 실을 자르자고 제안했다. 하지만 어떻게 잘라야 좋을지 몰라서 윤이에게 물어보기로 했다. 윤이와 함께 실을 어떻게 자르면 좋을지 계산해 주자!

입력

첫째 줄에 풍선의 개수 $N$과 실의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; 1 \le M \le 300\,000)$

다음 $M$개의 줄에 실이 잇는 풍선 또는 고리의 번호 쌍 $u$, $v$와 실의 길이 $w$가 공백으로 구분되어 주어진다. $(0 \le u, v \le N; u \ne v; 1 \le w \le 10^9)$

풍선의 번호는 $1$ 이상 $N$ 이하의 정수이고, 고리의 번호는 $0$이다. 같은 번호 쌍이 여러 번 주어질 수 있다.

모든 풍선은 실을 통해 고리에 직접 또는 간접적으로 연결되어 있음이 보장된다. 즉, 처음부터 멀리 날아가 버리는 풍선은 없다.

출력

잘라야 하는 실의 개수 $K$와 남은 실의 길이의 합 $L$을 공백으로 구분하여 출력한다.

예제 입력 1

2 3
0 1 3
1 2 5
0 2 10

예제 출력 1

1 8

예제 입력 2

4 4
0 1 20
1 2 30
2 3 40
2 4 50

예제 출력 2

0 140

예제 입력 3

3 7
0 1 3
0 1 10
0 2 2
2 1 1
1 3 7
3 2 8
3 0 11

예제 출력 3

4 13
W3sicHJvYmxlbV9pZCI6IjM1NDczIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNDhkXHVjMTIwXHVjOTA0IFx1Yzc5MFx1Yjk3NFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzI0XHVjNzc0XHVjNjQwIFx1YjJlY1x1YWQ2Y1x1YzY0MCBcdWQzZWNcdWIyYzlcdWMyYTRcdWIyOTQgXHViYzE0XHViMmU1XHVjNWQwIFx1YWNlMFx1YzgxNVx1YjQxYyBcdWFjZTBcdWI5YWNcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1ZDQ4ZFx1YzEyMFx1YWNmYyAkTSRcdWFjMWNcdWM3NTggXHVjMmU0XHVjNzQ0IFx1Yzc3NFx1YzViNFx1YzExYyBVRFBDXHViOTdjIFx1YzBjMVx1YzlkNVx1ZDU1OFx1YjI5NCBcdWM4NzBcdWQ2MTVcdWJiM2NcdWM3NDQgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMmU0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBcdWQ0OGRcdWMxMjBcdWFjZmMgXHVkNDhkXHVjMTIwLCBcdWI2MTBcdWIyOTQgXHVkNDhkXHVjMTIwXHVhY2ZjIFx1YWNlMFx1YjlhY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNDhkXHVjMTIwXHVjNzQwIFx1Yzc5MFx1YzJlMFx1YzVkMFx1YWM4YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVjMmU0IFx1YzkxMSBcdWM1YjRcdWIyOTAgXHVkNTU4XHViMDk4XHVhYzAwIFx1ZDMzZFx1ZDMzZFx1ZDU3NFx1YzljOCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjNzA0XHViODVjIFx1YjVhMFx1YzYyNFx1Yjk3OFx1YjJlNC4gXHVjMmU0XHVjNzc0IFx1YWYyY1x1Yzc3NFx1YWM3MFx1YjA5OCBcdWQ0OGRcdWMxMjBcdWIwN2NcdWI5YWMgXHViZDgwXHViNTJhXHVkNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHViYTcwLCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YmIzNFx1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjQ0XHVjMTMxXHViNDFjIFx1Yzg3MFx1ZDYxNVx1YmIzY1x1Yzc0NCBcdWMwYjRcdWQzYjRcdWJjZjRcdWIzNTggXHVkM2VjXHViMmM5XHVjMmE0XHViMjk0IFx1YzJlNFx1Yzc3NCBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWFjODMgXHVhYzE5XHVjNTQ0XHVjMTFjIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMmU0XHVjNzQ0IFx1Yzc5OFx1Yjc3Y1x1YjBiNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzJlNFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWFjZTAgXHViMDljIFx1YjRhNFx1YzVkMFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YmNjMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWQ0OGRcdWMxMjBcdWM3NzQgXHViYTQwXHViOWFjIFx1YjBhMFx1YzU0NFx1YWMwMCBcdWJjODRcdWI5YWNcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVkM2VjXHViMmM5XHVjMmE0XHViMjk0IFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWM3OThcdWI3N2NcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyZTRcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWMyZTRcdWM3NDQgXHVjNzkwXHViOTdjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmVjXHVhZDZjXHViMjk0IFx1YjBhOFx1Yzc0MCBcdWMyZTRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDZjXHViM2M0XHViODVkIFx1YzJlNFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWM3OTBcdWFjZTAgXHVjODFjXHVjNTQ4XHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNWI0XHViNWJiXHVhYzhjIFx1Yzc5OFx1Yjc3Y1x1YzU3YyBcdWM4OGJcdWM3NDRcdWM5YzAgXHViYWIwXHViNzdjXHVjMTFjIFx1YzcyNFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWJiM2NcdWM1YjRcdWJjZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3MjRcdWM3NzRcdWM2NDAgXHVkNTY4XHVhZWQ4IFx1YzJlNFx1Yzc0NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNzkwXHViOTc0XHViYTc0IFx1Yzg4Ylx1Yzc0NFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NzQgXHVjOGZjXHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4ICROJFx1YWNmYyBcdWMyZTRcdWM3NTggXHVhYzFjXHVjMjE4ICRNJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgTiBcXGxlIDEwMFxcLDAwMDsgMSBcXGxlIE0gXFxsZSAzMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE0kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWMyZTRcdWM3NzQgXHVjNzg3XHViMjk0IFx1ZDQ4ZFx1YzEyMCBcdWI2MTBcdWIyOTQgXHVhY2UwXHViOWFjXHVjNzU4IFx1YmM4OFx1ZDYzOCBcdWMzMGQgJHUkLCAkdiRcdWM2NDAgXHVjMmU0XHVjNzU4IFx1YWUzOFx1Yzc3NCAkdyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMCBcXGxlIHUsIHYgXFxsZSBOOyB1IFxcbmUgdjsgMSBcXGxlIHcgXFxsZSAxMF45KSQ8XC9wPlxyXG5cclxuPHA+XHVkNDhkXHVjMTIwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAkMSQgXHVjNzc0XHVjMGMxICROJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwLCBcdWFjZTBcdWI5YWNcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0ICQwJFx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YmM4OFx1ZDYzOCBcdWMzMGRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWMyZTRcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YWNlMFx1YjlhY1x1YzVkMCBcdWM5YzFcdWM4MTEgXHViNjEwXHViMjk0IFx1YWMwNFx1YzgxMVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzRjXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWNjOThcdWM3NGNcdWJkODBcdWQxMzAgXHViYTQwXHViOWFjIFx1YjBhMFx1YzU0NFx1YWMwMCBcdWJjODRcdWI5YWNcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3OThcdWI3N2NcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzJlNFx1Yzc1OCBcdWFjMWNcdWMyMTggJEskXHVjNjQwIFx1YjBhOFx1Yzc0MCBcdWMyZTRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OSAkTCRcdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzU0NzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDdXQgdGhlIEJhbGxvb24gU3RyaW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+WXVuZWUsIERhbGd1LCBhbmQgUG9uaXggYXJlIGJ1aWxkaW5nIGEgVURQQy10aGVtZWQgaW5zdGFsbGF0aW9uIHVzaW5nICRNJCBzdHJpbmdzIHRvIGNvbm5lY3QgJE4kIGJhbGxvb25zIGFuZCBhIHJpbmcgdGhhdCBpcyBmaXhlZCB0byB0aGUgZ3JvdW5kLiBBIHN0cmluZyBjYW4gY29ubmVjdCB0d28gYmFsbG9vbnMsIG9yIGEgYmFsbG9vbiBhbmQgdGhlIHJpbmcuIEVhY2ggYmFsbG9vbiByaXNlcyB1cHdhcmQgdW50aWwgb25lIG9mIHRoZSBzdHJpbmdzIGF0dGFjaGVkIHRvIGl0IGJlY29tZXMgdGlnaHQuIEFzc3VtZSB0aGF0IHN0cmluZ3MgbmV2ZXIgZ2V0IHRhbmdsZWQsIGJhbGxvb25zIG5ldmVyIGNvbGxpZGUgd2l0aCBlYWNoIG90aGVyLCBhbmQgdGhlIHNpemVzIG9mIHRoZSBiYWxsb29ucyBhcmUgbmVnbGlnaWJsZS48XC9wPlxyXG5cclxuPHA+V2hpbGUgbG9va2luZyBhdCB0aGUgY29tcGxldGVkIGluc3RhbGxhdGlvbiwgUG9uaXggdGhpbmtzIHRoZXJlIGFyZSB0b28gbWFueSBzdHJpbmdzIGFuZCBkZWNpZGVzIHRvIGN1dCB0aGUgdW5uZWNlc3Nhcnkgb25lcy4gQWZ0ZXIgY3V0dGluZyBzdHJpbmdzLCB0aGUgaGVpZ2h0cyBvZiB0aGUgYmFsbG9vbnMgbXVzdCBub3QgY2hhbmdlLCBhbmQgbm8gYmFsbG9vbiBtYXkgZmx5IGF3YXkuIFBvbml4IHdpbGwga2VlcCBjdXR0aW5nIHN0cmluZ3MgdW50aWwgdGhlcmUgYXJlIG5vIG1vcmUgc3RyaW5ncyB0aGF0IGNhbiBiZSBjdXQuPFwvcD5cclxuXHJcbjxwPkRhbGd1IHN1Z2dlc3RzIGN1dHRpbmcgdGhlIHN0cmluZ3Mgc28gdGhhdCB0aGUgc3VtIG9mIHRoZSBsZW5ndGhzIG9mIHRoZSByZW1haW5pbmcgc3RyaW5ncyBpcyBtYXhpbWl6ZWQuIEJ1dCBub3Qga25vd2luZyBob3cgdG8gZG8gdGhhdCwgRGFsZ3UgYXNrcyBZdW5lZSBmb3IgaGVscC4gTGV0JnJzcXVvO3MgaGVscCBZdW5lZSBkZXRlcm1pbmUgaG93IHRvIGN1dCB0aGUgc3RyaW5ncyE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgYmFsbG9vbnMgJE4kIGFuZCB0aGUgbnVtYmVyIG9mIHN0cmluZ3MgJE0kLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAkKDFcXGxlIE5cXGxlIDEwMFxcLCAwMDA7MVxcbGUgTVxcbGUgMzAwXFwsIDAwMCkkPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgJE0kIGxpbmVzIGNvbnRhaW5zIG51bWJlcnMgJHUkIGFuZCAkdiQsIGRlbm90aW5nIHRoZSBiYWxsb29uIG9yIHJpbmcgY29ubmVjdGVkIGJ5IGEgc3RyaW5nLCBhbmQgdGhlIHN0cmluZyBsZW5ndGggJHckLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAkKDBcXGxlIHUsdlxcbGUgTjt1XFxuZSB2OzFcXGxlIHdcXGxlIDEwXjkpJDxcL3A+XHJcblxyXG48cD5CYWxsb29uIG51bWJlcnMgYXJlIGludGVnZXJzIGZyb20gJDEkIHRocm91Z2ggJE4kLCBhbmQgdGhlIHJpbmcgaXMgbnVtYmVyZWQgJDAkLiBUaGUgc2FtZSBwYWlyIG9mIG51bWJlcnMgbWF5IGFwcGVhciBtdWx0aXBsZSB0aW1lcy48XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IGV2ZXJ5IGJhbGxvb24gaXMgZGlyZWN0bHkgb3IgaW5kaXJlY3RseSBjb25uZWN0ZWQgdG8gdGhlIHJpbmcgdGhyb3VnaCBzdHJpbmdzLiBJbiBvdGhlciB3b3Jkcywgbm8gYmFsbG9vbiBoYXMgYWxyZWFkeSBmbG93biBhd2F5IGF0IHRoZSBiZWdpbm5pbmcuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG51bWJlciBvZiBzdHJpbmdzIHRvIGN1dCwgJEskLCBhbmQgdGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiB0aGUgcmVtYWluaW5nIHN0cmluZ3MsICRMJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==