시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 256 80 57 32.386%

문제

“앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕국은 코끼리왕국을 공격하기로 결정하였다. 동물나라 지도에서 개미왕국은 1번 정점에 위치해 있고 코끼리왕국은 N번 정점에 위치해 있다. 따라서 개미왕국이 1번 정점에서 N번 정점으로 공격을 하러 가는 상황이다. (개미왕국은 최단거리로 이동을 하게 되고, 코끼리왕국은 움직이지 않는다)

“개미”와 “코끼리”의 앞 글자를 따서 이 전쟁은 “개코전쟁”으로 역사에 기억된다.

“앙두레 강”은 자신 때문에 발생한 이 전쟁을 어떻게든 막으려고 한다. 협상을 할 시간을 벌기 위해 개미왕국이 코끼리왕국에 도착하는 시간을 최대한 늦추려고 한다. 그래서 “앙두레 강”은 사자왕국의 도움을 빌어 도로 중 딱 하나를 파괴하려고 하는데 어느 도로를 파괴해야 개미왕국이 최단거리로 가더라도 그 거리를 최대로 할 수 있을까?

“앙두레 강”를 도와 1번 정점에서 N번 정점으로의 최단거리가 최대가 되도록 도로 하나를 파괴하도록 하자. (어떤 하나의 도로를 파괴하더라도 1번 정점에서 N번 정점으로 도달 가능하다)

입력

첫 줄에 N과 M이 입력된다. N은 정점의 개수이고 M은 도로의 수이다. (1 ≤ N ≤ 1000, 1 ≤ M ≤ N*(N-1)/2)

다음 줄부터 M개의 줄에 도로의 정보가 입력된다.

i+1번째 줄에는 i번째 도로의 정보 xi yi zi 가 입력되고 이 도로는 정점 xi와 정점 yi를 잇는 도로이며 지나는데 zi만큼의 시간이 걸린다는 것을 의미한다. 두 정점사이에는 두 개 이상의 길이 존재하지 않고 모든 도로는 양방향이며 한 도로를 파괴하는 것은 양방향의 길 모두를 파괴하는 것이다.

출력

적당한 도로하나를 파괴했을 때 1번 정점에서 N번 정점으로의 최단거리를 출력한다.

예제 입력 1

5 6
1 2 4
1 3 3
2 3 1
2 4 4
2 5 7
4 5 1

예제 출력 1

11
W3sicHJvYmxlbV9pZCI6IjIzMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWNmNTRcdWM4MDRcdWM3YzEiLCJkZXNjcmlwdGlvbiI6IjxwPiZsZHF1bztcdWM1NTlcdWI0NTBcdWI4MDggXHVhYzE1JnJkcXVvO1x1Yzc3NCBcdWFjMWNcdWJiZjhcdWM2NDAgXHVjZjU0XHViMDdjXHViOWFjIFx1YWNiMFx1ZDYzY1x1YzJkZFx1YzVkMFx1YzExYyBcdWFlMzBcdWNjMjhcdWI5N2MgXHVjNTQ0XHViOTg0XHViMmY1XHVhYzhjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjMmU0XHVkMzI4XHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMyZGRcdWM3YTVcdWM3NzQgXHVjNTQ0XHVjMjE4XHViNzdjXHVjN2E1XHVjNzc0IFx1YjQxOFx1YWNlMCBcdWFjYjBcdWQ2M2NcdWM3NzQgXHViYjNjXHVhYzcwXHVkNDg4XHVjNzc0IFx1YjQxOFx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVhZTA5XHVhZTMwXHVjNTdjXHViMjk0IFx1YzY1NVx1YWQ2ZCBcdWFjMDRcdWM1ZDAgXHViZDg0XHVjN2MxXHVjNzNjXHViODVjIFx1Yzc3NFx1YzViNFx1YzgzOCBcdWFjMWNcdWJiZjhcdWM2NTVcdWFkNmRcdWM3NDAgXHVjZjU0XHViMDdjXHViOWFjXHVjNjU1XHVhZDZkXHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YjNkOVx1YmIzY1x1YjA5OFx1Yjc3YyBcdWM5YzBcdWIzYzRcdWM1ZDBcdWMxMWMgXHVhYzFjXHViYmY4XHVjNjU1XHVhZDZkXHVjNzQwIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU3NCBcdWM3ODhcdWFjZTAgXHVjZjU0XHViMDdjXHViOWFjXHVjNjU1XHVhZDZkXHVjNzQwIE5cdWJjODggXHVjODE1XHVjODEwXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU3NCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWFjMWNcdWJiZjhcdWM2NTVcdWFkNmRcdWM3NzQgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgTlx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1ZDU1OFx1YjdlYyBcdWFjMDBcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0XHViMmU0LiAoXHVhYzFjXHViYmY4XHVjNjU1XHVhZDZkXHVjNzQwIFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVjZjU0XHViMDdjXHViOWFjXHVjNjU1XHVhZDZkXHVjNzQwIFx1YzZjMFx1YzljMVx1Yzc3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPiZsZHF1bztcdWFjMWNcdWJiZjgmcmRxdW87XHVjNjQwICZsZHF1bztcdWNmNTRcdWIwN2NcdWI5YWMmcmRxdW87XHVjNzU4IFx1YzU1ZSBcdWFlMDBcdWM3OTBcdWI5N2MgXHViNTMwXHVjMTFjIFx1Yzc3NCBcdWM4MDRcdWM3YzFcdWM3NDAgJmxkcXVvO1x1YWMxY1x1Y2Y1NFx1YzgwNFx1YzdjMSZyZHF1bztcdWM3M2NcdWI4NWMgXHVjNWVkXHVjMGFjXHVjNWQwIFx1YWUzMFx1YzViNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+JmxkcXVvO1x1YzU1OVx1YjQ1MFx1YjgwOCBcdWFjMTUmcmRxdW87XHVjNzQwIFx1Yzc5MFx1YzJlMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViYzFjXHVjMGRkXHVkNTVjIFx1Yzc3NCBcdWM4MDRcdWM3YzFcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjXHViNGUwIFx1YjljOVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDYxMVx1YzBjMVx1Yzc0NCBcdWQ1NjAgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YmM4Y1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzFjXHViYmY4XHVjNjU1XHVhZDZkXHVjNzc0IFx1Y2Y1NFx1YjA3Y1x1YjlhY1x1YzY1NVx1YWQ2ZFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWIyYTZcdWNkOTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgJmxkcXVvO1x1YzU1OVx1YjQ1MFx1YjgwOCBcdWFjMTUmcmRxdW87XHVjNzQwIFx1YzBhY1x1Yzc5MFx1YzY1NVx1YWQ2ZFx1Yzc1OCBcdWIzYzRcdWM2YzBcdWM3NDQgXHViZTRjXHVjNWI0IFx1YjNjNFx1Yjg1YyBcdWM5MTEgXHViNTMxIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWQzMGNcdWFkMzRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwIFx1YzViNFx1YjI5MCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTc0XHVjNTdjIFx1YWMxY1x1YmJmOFx1YzY1NVx1YWQ2ZFx1Yzc3NCBcdWNkNWNcdWIyZThcdWFjNzBcdWI5YWNcdWI4NWMgXHVhYzAwXHViMzU0XHViNzdjXHViM2M0IFx1YWRmOCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHViMzAwXHViODVjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcblxyXG48cD4mbGRxdW87XHVjNTU5XHViNDUwXHViODA4IFx1YWMxNSZyZHF1bztcdWI5N2MgXHViM2M0XHVjNjQwIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIE5cdWJjODggXHVjODE1XHVjODEwXHVjNzNjXHViODVjXHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjNjNFx1Yjg1YyBcdWQ1NThcdWIwOThcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1Yzc5MC4gKFx1YzViNFx1YjVhNCBcdWQ1NThcdWIwOThcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1ZDMwY1x1YWQzNFx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCAxXHViYzg4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBOXHViYzg4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWIzYzRcdWIyZWMgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0KTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBOXHVjNzQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAgTVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwLCAxICZsZTsgTSAmbGU7IE4qKE4tMSlcLzIpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0IHhpIHlpIHppIFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MThcdWFjZTAgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWM4MTVcdWM4MTAgeGlcdWM2NDAgXHVjODE1XHVjODEwIHlpXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NzRcdWJhNzAgXHVjOWMwXHViMDk4XHViMjk0XHViMzcwIHppXHViOWNjXHVkMDdjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzgxMFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWFlMzhcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNVx1Yzc3NFx1YmE3MCBcdWQ1NWMgXHViM2M0XHViODVjXHViOTdjIFx1ZDMwY1x1YWQzNFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzU4IFx1YWUzOCBcdWJhYThcdWI0NTBcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MDFcdWIyZjlcdWQ1NWMgXHViM2M0XHViODVjXHVkNTU4XHViMDk4XHViOTdjIFx1ZDMwY1x1YWQzNFx1ZDU4OFx1Yzc0NCBcdWI1NGMgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgTlx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWNcdWM3NTggXHVjZDVjXHViMmU4XHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUFSSUNBIiwiZGVzY3JpcHRpb24iOiI8cD5NYXJpY2EgaXMgdmVyeSBhbmdyeSB3aXRoIE1pcmtvIGJlY2F1c2UgaGUgZm91bmQgYSBuZXcgZ2lybGZyaWVuZCBhbmQgc2hlIHNlZWtzIHJldmVuZ2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNpbmNlIHNoZSBkb2VzbiYjMzk7dCBsaXZlIGluIHRoZSBzYW1lIGNpdHksIHNoZSBzdGFydGVkIHByZXBhcmluZyBmb3IgdGhlIGxvbmcgam91cm5leS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgdHdvIGNpdGllcyBpbiB0aGUgY291bnRyeSBhcmUgY29ubmVjdGVkIGJ5IGF0IG1vc3Qgb25lIHJvYWQsIGFuZCB3ZSBrbm93IGZvciBldmVyeSByb2FkIGhvdyBtYW55IG1pbnV0ZXMgaXQgdGFrZXMgdG8gY29tZSBmcm9tIG9uZSBjaXR5IHRvIGFub3RoZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIG92ZXJoZWFyZCBpbiB0aGUgY2FyIHRoYXQgb25lIG9mIHRoZSByb2FkcyBpcyB1bmRlciByZXBhaXJzLCBhbmQgdGhhdCBpdCBpcyBibG9ja2VkLCBidXQgZGlkbiYjMzk7dCBoZWFyIGV4YWN0bHkgd2hpY2ggcm9hZC4gSXQgaXMgcG9zc2libGUgdG8gY29tZSBmcm9tIE1hcmljYSYjMzk7cyBjaXR5IHRvIE1pcmtvJiMzOTtzIG5vIG1hdHRlciB3aGljaCByb2FkIGlzIGNsb3NlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWFyaWNhIHdpbGwgdHJhdmVsIG9ubHkgYnkgbm9uLWJsb2NrZWQgcm9hZHMsIGFuZCBzaGUgd2lsbCB0cmF2ZWwgYnkgc2hvcnRlc3Qgcm91dGUuIE1pcmtvIHdhbnRzIHRvIGtub3cgaG93IGxvbmcgd2lsbCBpdCB0YWtlIGZvciBoZXIgdG8gZ2V0IHRvIGhpcyBjaXR5IGluIHRoZSB3b3JzdCBjYXNlLCBzbyB0aGF0IGhlIGNvdWxkIG1ha2Ugc3VyZSB0aGF0IGhpcyBnaXJsZnJpZW5kIGlzIG91dCBvZiB0b3duIGZvciBsb25nIGVub3VnaC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgaGVscHMgTWlya28gaW4gZmluZGluZyBvdXQgd2hhdCBpcyB0aGUgbG9uZ2VzdCB0aW1lIGluIG1pbnV0ZXMgaXQgY291bGQgdGFrZSBmb3IgTWFyaWNhIHRvIGNvbWUgYnkgc2hvcnRlc3Qgcm91dGUgYnkgbm9uLWJsb2NrZWQgcm9hZHMgdG8gaGlzIGNpdHkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBhcmUgdHdvIG51bWJlcnMgaW4gdGhlIGZpcnN0IHJvdywgTiBhbmQgTSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCB0aGUgbnVtYmVyIG9mIHRvd25zLCBhbmQgdGhlIG51bWJlciBvZiByb2FkcyBiZXR3ZWVuIHRoZSB0b3ducy4gMSAmbGU7IE4gJmxlOyAxMDAwLCAxICZsZTsgTSAmbGU7IE4qKE4tMSlcLzIuIFRoZSBjaXRpZXMgYXJlIG1hcmtlZCB3aXRoIG51bWJlcnMgZnJvbSAxIHRvIE4sIE1pcmtvIGlzIGxvY2F0ZWQgaW4gY2l0eSAxLCBhbmQgTWFyaWNhIGluIGNpdHkgTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGhlIG5leHQgTSBsaW5lcyBhcmUgdGhyZWUgbnVtYmVycyBBLCBCIGFuZCBWLCBzZXBhcmF0ZWQgYnkgY29tbWFzLiAxICZsZTsgQSxCICZsZTsgTiwgMSAmbGU7IFYgJmxlOyAxMDAwLiBUaG9zZSBudW1iZXJzIG1lYW4gdGhhdCB0aGVyZSBpcyBhIHR3by13YXkgcm9hZCBiZXR3ZWVuIGNpdGllcyBBIGFuZCBCLCBhbmQgdGhhdCBpdCBpcyBjcm9zc2FibGUgaW4gViBtaW51dGVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBvdXRwdXQgZmlsZSB3cml0ZSB0aGUgbWF4aW11bSB0aW1lIGluIG1pbnV0ZXMsIGl0IGNvdWxkIHRha2UgTWFyaWNhIHRvIGNvbWUgdG8gTWlya28uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d