시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5721189320.946%

문제

지민이는 대지주 정문이 집에 놀러갔다. 하지만 테러리즘에 빠져있는 지민이는 가방 속에 한가득 지뢰를 들고 정문이 농장에 놀러 갔다.

이런 속마음도 모르는 정문이는 지민이에게 자신이 관리하는 N개의 농장을 관광시켜주려 한다. N개의 농장은 1번부터 N번까지 번호가 붙여져 있고 이 농장 사이에는 M개의 도로가 놓여있다.

현재 지민이와 정문이는 1번 농장에 있고 N번 농장을 방문한 다음 1번 농장으로 다시 돌아오려 한다. 그리고 방문하는 동안 지민이는 자신이 지나간 길에 지뢰를 심으려 한다.

지민이가 지뢰를 심는 사실이 발각되면 심각한 상황에 놓일 수 있기 때문에 가능한 한 빨리 농지를 관광하고 돌아오려 한다. 하지만 이미 지나간 길은 지뢰가 놓여 있기 때문에 다시 그 길을 지나가기를 원치 않는다.

지민이는 각 길마다 그 길을 지나가는 시간이 주어졌을 때 최소로 농지를 관광하고 돌아오는 시간을 알고 싶어 한다.

입력

첫째 줄에는 자연수 N(3 ≤ N ≤ 1,000), M(2 ≤ M ≤ 10,000)이 주어진다. N은 농지의 개수이고 M은 도로의 개수를 나타낸다. 다음 M개의 줄에는 도로의 정보를 나타내는 세 자연수 P, Q, L(1 ≤ L ≤ 35,000)이 주어진다. 이는 P번 도시와 Q번 도시 사이에 도로가 있으며, 이를 지날 때 소요되는 시간이 L임을 의미한다.

항상 농지를 관광하고 돌아올 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 농지를 관광하는 최소 시간을 출력한다.

예제 입력 1

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjE2NTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWJiZmNcdWM3NzRcdWM3NTggXHVkMTRjXHViN2VjIFNlYXNvbiBJSSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjOWMwXHViYmZjXHVjNzc0XHViMjk0IFx1YjMwMFx1YzljMFx1YzhmYyBcdWM4MTVcdWJiMzhcdWM3NzQgXHVjOWQxXHVjNWQwIFx1YjE4MFx1YjdlY1x1YWMxNFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDE0Y1x1YjdlY1x1YjlhY1x1Yzk5OFx1YzVkMCBcdWJlNjBcdWM4MzhcdWM3ODhcdWIyOTQgXHVjOWMwXHViYmZjXHVjNzc0XHViMjk0IFx1YWMwMFx1YmMyOSBcdWMxOGRcdWM1ZDAgXHVkNTVjXHVhYzAwXHViNGRkIFx1YzljMFx1YjhiMFx1Yjk3YyBcdWI0ZTRcdWFjZTAgXHVjODE1XHViYjM4XHVjNzc0IFx1YjE4ZFx1YzdhNVx1YzVkMCBcdWIxODBcdWI3ZWMgXHVhYzE0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZjAgXHVjMThkXHViOWM4XHVjNzRjXHViM2M0IFx1YmFhOFx1Yjk3NFx1YjI5NCBcdWM4MTVcdWJiMzhcdWM3NzRcdWIyOTQgXHVjOWMwXHViYmZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFkMDBcdWI5YWNcdWQ1NThcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIxOGRcdWM3YTVcdWM3NDQgXHVhZDAwXHVhZDExXHVjMmRjXHVjZjFjXHVjOGZjXHViODI0IFx1ZDU1Y1x1YjJlNC4gTlx1YWMxY1x1Yzc1OCBcdWIxOGRcdWM3YTVcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1ZWNcdWM4MzggXHVjNzg4XHVhY2UwIFx1Yzc3NCBcdWIxOGRcdWM3YTUgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHVhYzAwIFx1YjE5M1x1YzVlY1x1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjN2FjIFx1YzljMFx1YmJmY1x1Yzc3NFx1YzY0MCBcdWM4MTVcdWJiMzhcdWM3NzRcdWIyOTQgMVx1YmM4OCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVjNzg4XHVhY2UwIE5cdWJjODggXHViMThkXHVjN2E1XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWIyZTRcdWM3NGMgMVx1YmM4OCBcdWIxOGRcdWM3YTVcdWM3M2NcdWI4NWMgXHViMmU0XHVjMmRjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YzljMFx1YmJmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjOWMwXHViMDk4XHVhYzA0IFx1YWUzOFx1YzVkMCBcdWM5YzBcdWI4YjBcdWI5N2MgXHVjMmVjXHVjNzNjXHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHViYmZjXHVjNzc0XHVhYzAwIFx1YzljMFx1YjhiMFx1Yjk3YyBcdWMyZWNcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzc0IFx1YmMxY1x1YWMwMVx1YjQxOFx1YmE3NCBcdWMyZWNcdWFjMDFcdWQ1NWMgXHVjMGMxXHVkNjY5XHVjNWQwIFx1YjE5M1x1Yzc3YyBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YmU2OFx1YjlhYyBcdWIxOGRcdWM5YzBcdWI5N2MgXHVhZDAwXHVhZDExXHVkNTU4XHVhY2UwIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzRcdWJiZjggXHVjOWMwXHViMDk4XHVhYzA0IFx1YWUzOFx1Yzc0MCBcdWM5YzBcdWI4YjBcdWFjMDAgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMmU0XHVjMmRjIFx1YWRmOCBcdWFlMzhcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzAwXHVhZTMwXHViOTdjIFx1YzZkMFx1Y2U1OCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YmJmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVhZTM4XHViOWM4XHViMmU0IFx1YWRmOCBcdWFlMzhcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWIxOGRcdWM5YzBcdWI5N2MgXHVhZDAwXHVhZDExXHVkNTU4XHVhY2UwIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YzViNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOKDMgJmxlOyBOICZsZTsgMSwwMDApLCBNKDIgJmxlOyBNICZsZTsgMTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHViMThkXHVjOWMwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YWNlMCBNXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1Yzc5MFx1YzVmMFx1YzIxOCBQLCBRLCBMKDEgJmxlOyBMICZsZTsgMzUsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBQXHViYzg4IFx1YjNjNFx1YzJkY1x1YzY0MCBRXHViYzg4IFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzc0XHViOTdjIFx1YzljMFx1YjBhMCBcdWI1NGMgXHVjMThjXHVjNjk0XHViNDE4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBMXHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YjE4ZFx1YzljMFx1Yjk3YyBcdWFkMDBcdWFkMTFcdWQ1NThcdWFjZTAgXHViM2NjXHVjNTQ0XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIxOGRcdWM5YzBcdWI5N2MgXHVhZDAwXHVhZDExXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE2NTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGYXJtIFRvdXIiLCJkZXNjcmlwdGlvbiI6IjxwPldoZW4gRkomIzM5O3MgZnJpZW5kcyB2aXNpdCBoaW0gb24gdGhlIGZhcm0sIGhlIGxpa2VzIHRvIHNob3cgdGhlbSBhcm91bmQuIEhpcyBmYXJtIGNvbXByaXNlcyBOICgxICZsdDs9IE4gJmx0Oz0gMTAwMCkgZmllbGRzIG51bWJlcmVkIDEuLk4sIHRoZSBmaXJzdCBvZiB3aGljaCBjb250YWlucyBoaXMgaG91c2UgYW5kIHRoZSBOdGggb2Ygd2hpY2ggY29udGFpbnMgdGhlIGJpZyBiYXJuLiBBIHRvdGFsIE0gKDEgJmx0Oz0gTSAmbHQ7PSAxMDAwMCkgcGF0aHMgdGhhdCBjb25uZWN0IHRoZSBmaWVsZHMgaW4gdmFyaW91cyB3YXlzLiBFYWNoIHBhdGggY29ubmVjdHMgdHdvIGRpZmZlcmVudCBmaWVsZHMgYW5kIGhhcyBhIG5vbnplcm8gbGVuZ3RoIHNtYWxsZXIgdGhhbiAzNSwwMDAuPFwvcD5cclxuXHJcbjxwPlRvIHNob3cgb2ZmIGhpcyBmYXJtIGluIHRoZSBiZXN0IHdheSwgaGUgd2Fsa3MgYSB0b3VyIHRoYXQgc3RhcnRzIGF0IGhpcyBob3VzZSwgcG90ZW50aWFsbHkgdHJhdmVscyB0aHJvdWdoIHNvbWUgZmllbGRzLCBhbmQgZW5kcyBhdCB0aGUgYmFybi4gTGF0ZXIsIGhlIHJldHVybnMgKHBvdGVudGlhbGx5IHRocm91Z2ggc29tZSBmaWVsZHMpIGJhY2sgdG8gaGlzIGhvdXNlIGFnYWluLjxcL3A+XHJcblxyXG48cD5IZSB3YW50cyBoaXMgdG91ciB0byBiZSBhcyBzaG9ydCBhcyBwb3NzaWJsZSwgaG93ZXZlciBoZSBkb2VzbiYjMzk7dCB3YW50IHRvIHdhbGsgb24gYW55IGdpdmVuIHBhdGggbW9yZSB0aGFuIG9uY2UuIENhbGN1bGF0ZSB0aGUgc2hvcnRlc3QgdG91ciBwb3NzaWJsZS4gRkogaXMgc3VyZSB0aGF0IHNvbWUgdG91ciBleGlzdHMgZm9yIGFueSBnaXZlbiBmYXJtLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIE0uPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk0rMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHRoYXQgZGVmaW5lIGEgcGF0aDogVGhlIHN0YXJ0aW5nIGZpZWxkLCB0aGUgZW5kIGZpZWxkLCBhbmQgdGhlIHBhdGgmIzM5O3MgbGVuZ3RoLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IHRvdXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO February 2003 Contest > Green 4번

  • 문제를 번역한 사람: author6
  • 빠진 조건을 찾은 사람: thak00
  • 문제의 오타를 찾은 사람: zxcv551133