시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 27 17 17 80.952%

문제

두 도시 사이에 도로를 만드는 일은 매우 비싸다. 때문에 북쪽나라는 특정 도시를 두 번 이상 지나가지 않고서 임의의 두 도시간을 이동하는 경로가 유일하도록 도로가 설계되어 있다.

또한 북쪽나라의 모든 도시는 다른 모든 도시로 이동할 수 있다고 한다. 이 때, 거리가 가장 먼 두 도시 사이의 거리를 출력하는 것이 당신의 임무이다.

북쪽나라에는 최대 10,000개의 도시가 있을 수 있고, 도시는 1 부터 숫자로 이름이 매겨져 있다.

입력

입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 양방향으로 통행이 가능하다.

출력

가장 거리가 먼 두 도시간의 거리를 나타내는 정수 하나를 출력하면 된다.

예제 입력 1

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

예제 출력 1

22
W3sicHJvYmxlbV9pZCI6IjE1OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODFcdWNhYmRcdWIwOThcdWI3N2NcdWM3NTggXHViM2M0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc3Y1x1Yzc0MCZuYnNwO1x1YjllNFx1YzZiMCBcdWJlNDRcdWMyZjhcdWIyZTQuIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJkODFcdWNhYmRcdWIwOThcdWI3N2NcdWIyOTQgXHVkMmI5XHVjODE1IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM5YzBcdWIwOThcdWFjMDBcdWM5YzAgXHVjNTRhXHVhY2UwXHVjMTFjJm5ic3A7XHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3MjBcdWM3N2NcdWQ1NThcdWIzYzRcdWI4NWQgXHViM2M0XHViODVjXHVhYzAwIFx1YzEyNFx1YWNjNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWJkODFcdWNhYmRcdWIwOThcdWI3N2NcdWM3NTggXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1YjI5NCBcdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWM3MFx1YjlhY1x1YWMwMCBcdWFjMDBcdWM3YTUgXHViYTNjIFx1YjQ1MCBcdWIzYzRcdWMyZGMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWM3ODRcdWJiMzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ4MVx1Y2FiZFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAsMDAwXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViM2M0XHVjMmRjXHViMjk0IDEgXHViZDgwXHVkMTMwIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI5ODRcdWM3NzQgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhYzAxXHVhYzAxXHVjNzQwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQxYjVcdWQ1ODlcdWM3NzQmbmJzcDtcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHVjN2E1IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWJhM2MgXHViNDUwIFx1YjNjNFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNTk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUm9hZHMgaW4gdGhlIE5vcnRoIiwiZGVzY3JpcHRpb24iOiI8cD5CdWlsZGluZyBhbmQgbWFpbnRhaW5pbmcgcm9hZHMgYW1vbmcgY29tbXVuaXRpZXMgaW4gdGhlIGZhciBOb3J0aCBpcyBhbiBleHBlbnNpdmUgYnVzaW5lc3MuIFdpdGggdGhpcyBpbiBtaW5kLCB0aGUgcm9hZHMgYXJlIGJ1aWxkIHN1Y2ggdGhhdCB0aGVyZSBpcyBvbmx5IG9uZSByb3V0ZSBmcm9tIGEgdmlsbGFnZSB0byBhIHZpbGxhZ2UgdGhhdCBkb2VzIG5vdCBwYXNzIHRocm91Z2ggc29tZSBvdGhlciB2aWxsYWdlIHR3aWNlLjxcL3A+XHJcblxyXG48cD5HaXZlbiBpcyBhbiBhcmVhIGluIHRoZSBmYXIgTm9ydGggY29tcHJpc2luZyBhIG51bWJlciBvZiB2aWxsYWdlcyBhbmQgcm9hZHMgYW1vbmcgdGhlbSBzdWNoIHRoYXQgYW55IHZpbGxhZ2UgY2FuIGJlIHJlYWNoZWQgYnkgcm9hZCBmcm9tIGFueSBvdGhlciB2aWxsYWdlLiBZb3VyIGpvYiBpcyB0byBmaW5kIHRoZSByb2FkIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR3byBtb3N0IHJlbW90ZSB2aWxsYWdlcyBpbiB0aGUgYXJlYS48XC9wPlxyXG5cclxuPHA+VGhlIGFyZWEgaGFzIHVwIHRvIDEwLDAwMCB2aWxsYWdlcyBjb25uZWN0ZWQgYnkgcm9hZCBzZWdtZW50cy4gVGhlIHZpbGxhZ2VzIGFyZSBudW1iZXJlZCBmcm9tIDEuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB0byB0aGUgcHJvYmxlbSBpcyBhIHNlcXVlbmNlIG9mIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgdGhyZWUgcG9zaXRpdmUgaW50ZWdlcnM6IHRoZSBudW1iZXIgb2YgYSB2aWxsYWdlLCB0aGUgbnVtYmVyIG9mIGEgZGlmZmVyZW50IHZpbGxhZ2UsIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSByb2FkIHNlZ21lbnQgY29ubmVjdGluZyB0aGUgdmlsbGFnZXMgaW4ga2lsb21ldGVycy4gQWxsIHJvYWQgc2VnbWVudHMgYXJlIHR3by13YXkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91IGFyZSB0byBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlcjogdGhlIHJvYWQgZGlzdGFuY2UgYmV0d2VlbiB0aGUgdHdvIG1vc3QgcmVtb3RlIHZpbGxhZ2VzIGluIHRoZSBhcmVhLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==