시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB138956040040.120%

문제

“앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕국은 코끼리왕국을 공격하기로 결정하였다. 동물나라 지도에서 개미왕국은 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 ≤ xi, yi ≤ N, 1 ≤ zi ≤ 1000)

출력

적당한 도로하나를 파괴했을 때 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

예제 입력 2

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

예제 출력 2

13

예제 입력 3

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

예제 출력 3

27
W3sicHJvYmxlbV9pZCI6IjIzMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWNmNTRcdWM4MDRcdWM3YzEiLCJkZXNjcmlwdGlvbiI6IjxwPiZsZHF1bztcdWM1NTlcdWI0NTBcdWI4MDggXHVhYzE1JnJkcXVvO1x1Yzc3NCBcdWFjMWNcdWJiZjhcdWM2NDAgXHVjZjU0XHViMDdjXHViOWFjIFx1YWNiMFx1ZDYzY1x1YzJkZFx1YzVkMFx1YzExYyBcdWFlMzBcdWNjMjhcdWI5N2MgXHVjNTQ0XHViOTg0XHViMmY1XHVhYzhjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjMmU0XHVkMzI4XHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMyZGRcdWM3YTVcdWM3NzQgXHVjNTQ0XHVjMjE4XHViNzdjXHVjN2E1XHVjNzc0IFx1YjQxOFx1YWNlMCBcdWFjYjBcdWQ2M2NcdWM3NzQgXHViYjNjXHVhYzcwXHVkNDg4XHVjNzc0IFx1YjQxOFx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVhZTA5XHVhZTMwXHVjNTdjXHViMjk0IFx1YzY1NVx1YWQ2ZCBcdWFjMDRcdWM1ZDAgXHViZDg0XHVjN2MxXHVjNzNjXHViODVjIFx1Yzc3NFx1YzViNFx1YzgzOCBcdWFjMWNcdWJiZjhcdWM2NTVcdWFkNmRcdWM3NDAgXHVjZjU0XHViMDdjXHViOWFjXHVjNjU1XHVhZDZkXHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YjNkOVx1YmIzY1x1YjA5OFx1Yjc3YyBcdWM5YzBcdWIzYzRcdWM1ZDBcdWMxMWMgXHVhYzFjXHViYmY4XHVjNjU1XHVhZDZkXHVjNzQwIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU3NCBcdWM3ODhcdWFjZTAgXHVjZjU0XHViMDdjXHViOWFjXHVjNjU1XHVhZDZkXHVjNzQwIE5cdWJjODggXHVjODE1XHVjODEwXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU3NCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWFjMWNcdWJiZjhcdWM2NTVcdWFkNmRcdWM3NzQgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgTlx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1ZDU1OFx1YjdlYyBcdWFjMDBcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0XHViMmU0LiAoXHVhYzFjXHViYmY4XHVjNjU1XHVhZDZkXHVjNzQwIFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVjZjU0XHViMDdjXHViOWFjXHVjNjU1XHVhZDZkXHVjNzQwIFx1YzZjMFx1YzljMVx1Yzc3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPiZsZHF1bztcdWFjMWNcdWJiZjgmcmRxdW87XHVjNjQwICZsZHF1bztcdWNmNTRcdWIwN2NcdWI5YWMmcmRxdW87XHVjNzU4IFx1YzU1ZSBcdWFlMDBcdWM3OTBcdWI5N2MgXHViNTMwXHVjMTFjIFx1Yzc3NCBcdWM4MDRcdWM3YzFcdWM3NDAgJmxkcXVvO1x1YWMxY1x1Y2Y1NFx1YzgwNFx1YzdjMSZyZHF1bztcdWM3M2NcdWI4NWMgXHVjNWVkXHVjMGFjXHVjNWQwIFx1YWUzMFx1YzViNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+JmxkcXVvO1x1YzU1OVx1YjQ1MFx1YjgwOCBcdWFjMTUmcmRxdW87XHVjNzQwIFx1Yzc5MFx1YzJlMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViYzFjXHVjMGRkXHVkNTVjIFx1Yzc3NCBcdWM4MDRcdWM3YzFcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjXHViNGUwIFx1YjljOVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDYxMVx1YzBjMVx1Yzc0NCBcdWQ1NjAgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YmM4Y1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzFjXHViYmY4XHVjNjU1XHVhZDZkXHVjNzc0IFx1Y2Y1NFx1YjA3Y1x1YjlhY1x1YzY1NVx1YWQ2ZFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWIyYTZcdWNkOTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgJmxkcXVvO1x1YzU1OVx1YjQ1MFx1YjgwOCBcdWFjMTUmcmRxdW87XHVjNzQwIFx1YzBhY1x1Yzc5MFx1YzY1NVx1YWQ2ZFx1Yzc1OCBcdWIzYzRcdWM2YzBcdWM3NDQgXHViZTRjXHVjNWI0IFx1YjNjNFx1Yjg1YyBcdWM5MTEgXHViNTMxIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWQzMGNcdWFkMzRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwIFx1YzViNFx1YjI5MCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTc0XHVjNTdjIFx1YWMxY1x1YmJmOFx1YzY1NVx1YWQ2ZFx1Yzc3NCBcdWNkNWNcdWIyZThcdWFjNzBcdWI5YWNcdWI4NWMgXHVhYzAwXHViMzU0XHViNzdjXHViM2M0IFx1YWRmOCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHViMzAwXHViODVjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcblxyXG48cD4mbGRxdW87XHVjNTU5XHViNDUwXHViODA4IFx1YWMxNSZyZHF1bztcdWI5N2MgXHViM2M0XHVjNjQwIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIE5cdWJjODggXHVjODE1XHVjODEwXHVjNzNjXHViODVjXHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjNjNFx1Yjg1YyBcdWQ1NThcdWIwOThcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1Yzc5MC4gKFx1YzViNFx1YjVhNCBcdWQ1NThcdWIwOThcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1ZDMwY1x1YWQzNFx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCAxXHViYzg4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBOXHViYzg4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWIzYzRcdWIyZWMgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0KTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBOXHVjNzQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAgTVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwLCAxICZsZTsgTSAmbGU7IE4mdGltZXM7KE4tMSlcLzIpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0IHg8c3ViPmk8XC9zdWI+IHk8c3ViPmk8XC9zdWI+IHo8c3ViPmk8XC9zdWI+XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxOFx1YWNlMCBcdWM3NzQgXHViM2M0XHViODVjXHViMjk0IFx1YzgxNVx1YzgxMCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWM4MTVcdWM4MTAgeTxzdWI+aTxcL3N1Yj5cdWI5N2MgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc3NFx1YmE3MCBcdWM5YzBcdWIwOThcdWIyOTRcdWIzNzAgejxzdWI+aTxcL3N1Yj5cdWI5Y2NcdWQwN2NcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWI0NTAgXHVjODE1XHVjODEwXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWUzOFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzc0XHViYTcwIFx1ZDU1YyBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3NTggXHVhZTM4IFx1YmFhOFx1YjQ1MFx1Yjk3YyBcdWQzMGNcdWFkMzRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiAoMSAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyB6PHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjODAxXHViMmY5XHVkNTVjIFx1YjNjNFx1Yjg1Y1x1ZDU1OFx1YjA5OFx1Yjk3YyBcdWQzMGNcdWFkMzRcdWQ1ODhcdWM3NDQgXHViNTRjIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIE5cdWJjODggXHVjODE1XHVjODEwXHVjNzNjXHViODVjXHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjMyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BUklDQSIsImRlc2NyaXB0aW9uIjoiPHA+TWFyaWNhIGlzIHZlcnkgYW5ncnkgd2l0aCBNaXJrbyBiZWNhdXNlIGhlIGZvdW5kIGEgbmV3IGdpcmxmcmllbmQgYW5kIHNoZSBzZWVrcyByZXZlbmdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TaW5jZSBzaGUgZG9lc24mIzM5O3QgbGl2ZSBpbiB0aGUgc2FtZSBjaXR5LCBzaGUgc3RhcnRlZCBwcmVwYXJpbmcgZm9yIHRoZSBsb25nIGpvdXJuZXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IHR3byBjaXRpZXMgaW4gdGhlIGNvdW50cnkgYXJlIGNvbm5lY3RlZCBieSBhdCBtb3N0IG9uZSByb2FkLCBhbmQgd2Uga25vdyBmb3IgZXZlcnkgcm9hZCBob3cgbWFueSBtaW51dGVzIGl0IHRha2VzIHRvIGNvbWUgZnJvbSBvbmUgY2l0eSB0byBhbm90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBvdmVyaGVhcmQgaW4gdGhlIGNhciB0aGF0IG9uZSBvZiB0aGUgcm9hZHMgaXMgdW5kZXIgcmVwYWlycywgYW5kIHRoYXQgaXQgaXMgYmxvY2tlZCwgYnV0IGRpZG4mIzM5O3QgaGVhciBleGFjdGx5IHdoaWNoIHJvYWQuIEl0IGlzIHBvc3NpYmxlIHRvIGNvbWUgZnJvbSBNYXJpY2EmIzM5O3MgY2l0eSB0byBNaXJrbyYjMzk7cyBubyBtYXR0ZXIgd2hpY2ggcm9hZCBpcyBjbG9zZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1hcmljYSB3aWxsIHRyYXZlbCBvbmx5IGJ5IG5vbi1ibG9ja2VkIHJvYWRzLCBhbmQgc2hlIHdpbGwgdHJhdmVsIGJ5IHNob3J0ZXN0IHJvdXRlLiBNaXJrbyB3YW50cyB0byBrbm93IGhvdyBsb25nIHdpbGwgaXQgdGFrZSBmb3IgaGVyIHRvIGdldCB0byBoaXMgY2l0eSBpbiB0aGUgd29yc3QgY2FzZSwgc28gdGhhdCBoZSBjb3VsZCBtYWtlIHN1cmUgdGhhdCBoaXMgZ2lybGZyaWVuZCBpcyBvdXQgb2YgdG93biBmb3IgbG9uZyBlbm91Z2guJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGhlbHBzIE1pcmtvIGluIGZpbmRpbmcgb3V0IHdoYXQgaXMgdGhlIGxvbmdlc3QgdGltZSBpbiBtaW51dGVzIGl0IGNvdWxkIHRha2UgZm9yIE1hcmljYSB0byBjb21lIGJ5IHNob3J0ZXN0IHJvdXRlIGJ5IG5vbi1ibG9ja2VkIHJvYWRzIHRvIGhpcyBjaXR5LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgYXJlIHR3byBudW1iZXJzIGluIHRoZSBmaXJzdCByb3csIE4gYW5kIE0sIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgdGhlIG51bWJlciBvZiB0b3ducywgYW5kIHRoZSBudW1iZXIgb2Ygcm9hZHMgYmV0d2VlbiB0aGUgdG93bnMuIDEgJmxlOyBOICZsZTsgMTAwMCwgMSAmbGU7IE0gJmxlOyBOKihOLTEpXC8yLiBUaGUgY2l0aWVzIGFyZSBtYXJrZWQgd2l0aCBudW1iZXJzIGZyb20gMSB0byBOLCBNaXJrbyBpcyBsb2NhdGVkIGluIGNpdHkgMSwgYW5kIE1hcmljYSBpbiBjaXR5IE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBuZXh0IE0gbGluZXMgYXJlIHRocmVlIG51bWJlcnMgQSwgQiBhbmQgViwgc2VwYXJhdGVkIGJ5IGNvbW1hcy4gMSAmbGU7IEEsQiAmbGU7IE4sIDEgJmxlOyBWICZsZTsgMTAwMC4gVGhvc2UgbnVtYmVycyBtZWFuIHRoYXQgdGhlcmUgaXMgYSB0d28td2F5IHJvYWQgYmV0d2VlbiBjaXRpZXMgQSBhbmQgQiwgYW5kIHRoYXQgaXQgaXMgY3Jvc3NhYmxlIGluIFYgbWludXRlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUgd3JpdGUgdGhlIG1heGltdW0gdGltZSBpbiBtaW51dGVzLCBpdCBjb3VsZCB0YWtlIE1hcmljYSB0byBjb21lIHRvIE1pcmtvLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=