시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjE1OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODFcdWNhYmRcdWIwOThcdWI3N2NcdWM3NTggXHViM2M0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc3Y1x1Yzc0MCZuYnNwO1x1YjllNFx1YzZiMCBcdWJlNDRcdWMyZjhcdWIyZTQuIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJkODFcdWNhYmRcdWIwOThcdWI3N2NcdWIyOTQgXHVkMmI5XHVjODE1IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM5YzBcdWIwOThcdWFjMDBcdWM5YzAgXHVjNTRhXHVhY2UwXHVjMTFjJm5ic3A7XHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3MjBcdWM3N2NcdWQ1NThcdWIzYzRcdWI4NWQgXHViM2M0XHViODVjXHVhYzAwIFx1YzEyNFx1YWNjNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWJkODFcdWNhYmRcdWIwOThcdWI3N2NcdWM3NTggXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1YjI5NCBcdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzcwXHViOWFjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHViMmY5XHVjMmUwXHVjNzU4IFx1Yzc4NFx1YmIzNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDgxXHVjYWJkXHViMDk4XHViNzdjXHVjNWQwXHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMCwwMDBcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWIzYzRcdWMyZGNcdWIyOTQgMSBcdWJkODBcdWQxMzAgXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDFcdWFjMDFcdWM3NDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHViNDUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1ZDFiNVx1ZDU4OVx1Yzc3NCZuYnNwO1x1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3YTUgXHVhYzcwXHViOWFjXHVhYzAwIFx1YmEzYyBcdWI0NTAgXHViM2M0XHVjMmRjXHVhYzA0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE1OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSb2FkcyBpbiB0aGUgTm9ydGgiLCJkZXNjcmlwdGlvbiI6IjxwPkJ1aWxkaW5nIGFuZCBtYWludGFpbmluZyByb2FkcyBhbW9uZyBjb21tdW5pdGllcyBpbiB0aGUgZmFyIE5vcnRoIGlzIGFuIGV4cGVuc2l2ZSBidXNpbmVzcy4gV2l0aCB0aGlzIGluIG1pbmQsIHRoZSByb2FkcyBhcmUgYnVpbGQgc3VjaCB0aGF0IHRoZXJlIGlzIG9ubHkgb25lIHJvdXRlIGZyb20gYSB2aWxsYWdlIHRvIGEgdmlsbGFnZSB0aGF0IGRvZXMgbm90IHBhc3MgdGhyb3VnaCBzb21lIG90aGVyIHZpbGxhZ2UgdHdpY2UuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGlzIGFuIGFyZWEgaW4gdGhlIGZhciBOb3J0aCBjb21wcmlzaW5nIGEgbnVtYmVyIG9mIHZpbGxhZ2VzIGFuZCByb2FkcyBhbW9uZyB0aGVtIHN1Y2ggdGhhdCBhbnkgdmlsbGFnZSBjYW4gYmUgcmVhY2hlZCBieSByb2FkIGZyb20gYW55IG90aGVyIHZpbGxhZ2UuIFlvdXIgam9iIGlzIHRvIGZpbmQgdGhlIHJvYWQgZGlzdGFuY2UgYmV0d2VlbiB0aGUgdHdvIG1vc3QgcmVtb3RlIHZpbGxhZ2VzIGluIHRoZSBhcmVhLjxcL3A+XHJcblxyXG48cD5UaGUgYXJlYSBoYXMgdXAgdG8gMTAsMDAwIHZpbGxhZ2VzIGNvbm5lY3RlZCBieSByb2FkIHNlZ21lbnRzLiBUaGUgdmlsbGFnZXMgYXJlIG51bWJlcmVkIGZyb20gMS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHRvIHRoZSBwcm9ibGVtIGlzIGEgc2VxdWVuY2Ugb2YgbGluZXMsIGVhY2ggY29udGFpbmluZyB0aHJlZSBwb3NpdGl2ZSBpbnRlZ2VyczogdGhlIG51bWJlciBvZiBhIHZpbGxhZ2UsIHRoZSBudW1iZXIgb2YgYSBkaWZmZXJlbnQgdmlsbGFnZSwgYW5kIHRoZSBsZW5ndGggb2YgdGhlIHJvYWQgc2VnbWVudCBjb25uZWN0aW5nIHRoZSB2aWxsYWdlcyBpbiBraWxvbWV0ZXJzLiBBbGwgcm9hZCBzZWdtZW50cyBhcmUgdHdvLXdheS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3UgYXJlIHRvIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgcm9hZCBkaXN0YW5jZSBiZXR3ZWVuIHRoZSB0d28gbW9zdCByZW1vdGUgdmlsbGFnZXMgaW4gdGhlIGFyZWEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d