시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 485 123 70 21.407%

문제

봄캠프 기간 동안 고속도로의 통행료가 급격하게 올라, 참가자들이 자칫 집으로 돌아가지 못할 수도 있는 위기에 봉착했다! 통행료가 인하되기 전까지는 여기 속초에서 원쌤과 함께 계속 프로그래밍 공부를 해야 할 수도 있는 상황인 것이다! 이 모든 것은 귀가시에 사용할 교통비를, 고속도로 통행료가 오르기 전에 계산해서 들고 왔기 때문이다.

다급해진 여러분은 정해진 예산을 가지고 집으로 돌아갈 수 있을지 알아보고, 갈 수 있다면 그에 필요한 최단 이동거리를 계산하려고 한다. 이를 해결하기 위한 프로그램을 작성하라.

입력

첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 주어지는데, 각 줄은 네 개의 숫자 s, d, l, t로 이루어져 있다. s는 도로의 출발 도시 번호이고, d는 도로의 도착 도시 번호이다. l은 도로의 길이이고, t는 도로의 통행료이다. (1≤s≤N, 1≤d≤N, 1≤l≤100, 0≤t≤100)

도시의 번호는 1번부터 N번까지 빠짐없이 붙어 있다. 이곳 속초는 1번 도시이고, 여러분의 집은 N번 도시에 있다. 각 도로는 일방통행로이다. 서로 다른 두 도로가 서로 같은 시작 도시와 서로 같은 도착 도시를 가질 수 있음에 유의하라.

출력

첫 줄에 정해진 예산 내에서 이용할 수 있는 경로 중 제일 짧은 것의 길이를 출력한다. 만약 가능한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

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

예제 출력 1

11
W3sicHJvYmxlbV9pZCI6IjE4ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmQwNFx1Y2VhMFx1ZDUwNCBcdWFlMzBcdWFjMDQgXHViM2Q5XHVjNTQ4IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWFjMDAgXHVhZTA5XHVhY2E5XHVkNTU4XHVhYzhjIFx1YzYyY1x1Yjc3YywgXHVjYzM4XHVhYzAwXHVjNzkwXHViNGU0XHVjNzc0IFx1Yzc5MFx1Y2U2YiBcdWM5ZDFcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHVjOWMwIFx1YmFiYlx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMjk0IFx1YzcwNFx1YWUzMFx1YzVkMCBcdWJkMDlcdWNjMjlcdWQ1ODhcdWIyZTQhIFx1ZDFiNVx1ZDU4OVx1YjhjY1x1YWMwMCBcdWM3NzhcdWQ1NThcdWI0MThcdWFlMzAgXHVjODA0XHVhZTRjXHVjOWMwXHViMjk0IFx1YzVlY1x1YWUzMCBcdWMxOGRcdWNkMDhcdWM1ZDBcdWMxMWMgXHVjNmQwXHVjMzI0XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWFjYzRcdWMxOGQgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc4IFx1YWM4M1x1Yzc3NFx1YjJlNCEgXHVjNzc0IFx1YmFhOFx1YjRlMCBcdWFjODNcdWM3NDAgXHVhZGMwXHVhYzAwXHVjMmRjXHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWFkNTBcdWQxYjVcdWJlNDRcdWI5N2MsIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWFjMDAgXHVjNjI0XHViOTc0XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWFjYzRcdWMwYjBcdWQ1NzRcdWMxMWMgXHViNGU0XHVhY2UwIFx1YzY1NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1YWUwOVx1ZDU3NFx1YzljNCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHVjODE1XHVkNTc0XHVjOWM0IFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjOWQxXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YWMwOCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YmNmNFx1YWNlMCwgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4XHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWIyZTggXHVjNzc0XHViM2Q5XHVhYzcwXHViOWFjXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWM5MDBcdWJlNDRcdWQ1NzQgXHViNDU0IFx1YWQ1MFx1ZDFiNVx1YmU0NCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAmbGU7SyZsZTsxMCwwMDApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWFjZmMgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDEgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzIyYlx1Yzc5MCBOXHVhY2ZjIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyMmJcdWM3OTAgUlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyJmxlO04mbGU7MTAwLCAxJmxlO1ImbGU7MTAsMDAwKSBcdWM3NzRcdWQ2YzQgUlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIHMsIGQsIGwsIHRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gc1x1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjZDljXHViYzFjIFx1YjNjNFx1YzJkYyBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIGRcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YjNjNFx1Y2MyOSBcdWIzYzRcdWMyZGMgXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LiBsXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWFjZTAsIHRcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1ZDFiNVx1ZDU4OVx1YjhjY1x1Yzc3NFx1YjJlNC4gKDEmbGU7cyZsZTtOLCAxJmxlO2QmbGU7TiwgMSZsZTtsJmxlOzEwMCwgMCZsZTt0JmxlOzEwMCk8XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViZTYwXHVjOWQwXHVjNWM2XHVjNzc0IFx1YmQ5OVx1YzViNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YWNmMyBcdWMxOGRcdWNkMDhcdWIyOTQgMVx1YmM4OCBcdWIzYzRcdWMyZGNcdWM3NzRcdWFjZTAsIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc1OCBcdWM5ZDFcdWM3NDAgTlx1YmM4OCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViM2M0XHViODVjXHViMjk0IFx1Yzc3Y1x1YmMyOVx1ZDFiNVx1ZDU4OVx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViM2M0XHViODVjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjMTlcdWM3NDAgXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YzY0MCBcdWMxMWNcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YjNjNFx1Y2MyOSBcdWIzYzRcdWMyZGNcdWI5N2MgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3NGNcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjODE1XHVkNTc0XHVjOWM0IFx1YzYwOFx1YzBiMCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHVjNzc0XHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjIFx1YzkxMSBcdWM4MWNcdWM3N2MgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM1YzZcdWM3NDQgXHViNTRjXHVjNWQwXHViMjk0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUm9hZHMiLCJkZXNjcmlwdGlvbiI6IjxwPk4gY2l0aWVzIG5hbWVkIHdpdGggbnVtYmVycyAxIC4uLiBOIGFyZSBjb25uZWN0ZWQgd2l0aCBvbmUtd2F5IHJvYWRzLiBFYWNoIHJvYWQgaGFzIHR3byBwYXJhbWV0ZXJzIGFzc29jaWF0ZWQgd2l0aCBpdDogdGhlIHJvYWQgbGVuZ3RoIGFuZCB0aGUgdG9sbCB0aGF0IG5lZWRzIHRvIGJlIHBhaWQgZm9yIHRoZSByb2FkIChleHByZXNzZWQgaW4gdGhlIG51bWJlciBvZiBjb2lucykuPFwvcD5cclxuXHJcbjxwPkJvYiBhbmQgQWxpY2UgdXNlZCB0byBsaXZlIGluIHRoZSBjaXR5IDEuIEFmdGVyIG5vdGljaW5nIHRoYXQgQWxpY2Ugd2FzIGNoZWF0aW5nIGluIHRoZSBjYXJkIGdhbWUgdGhleSBsaWtlZCB0byBwbGF5LCBCb2IgYnJva2UgdXAgd2l0aCBoZXIgYW5kIGRlY2lkZWQgdG8gbW92ZSBhd2F5IC0gdG8gdGhlIGNpdHkgTi4gSGUgd2FudHMgdG8gZ2V0IHRoZXJlIGFzIHF1aWNrbHkgYXMgcG9zc2libGUsIGJ1dCBoZSBpcyBzaG9ydCBvbiBjYXNoLjxcL3A+XHJcblxyXG48cD5XZSB3YW50IHRvIGhlbHAgQm9iIHRvIGZpbmQgdGhlIHNob3J0ZXN0IHBhdGggZnJvbSB0aGUgY2l0eSAxIHRvIHRoZSBjaXR5IE4gdGhhdCBoZSBjYW4gYWZmb3JkIHdpdGggdGhlIGFtb3VudCBvZiBtb25leSBoZSBoYXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgSywgMCZsdDs9SyZsdDs9MTAwMDAsIG1heGltdW0gbnVtYmVyIG9mIGNvaW5zIHRoYXQgQm9iIGNhbiBzcGVuZCBvbiBoaXMgd2F5LjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiwgMiZsdDs9TiZsdDs9MTAwLCB0aGUgdG90YWwgbnVtYmVyIG9mIGNpdGllcy48XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgUiwgMSZsdDs9UiZsdDs9MTAwMDAsIHRoZSB0b3RhbCBudW1iZXIgb2Ygcm9hZHMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIGxpbmVzIGRlc2NyaWJlcyBvbmUgcm9hZCBieSBzcGVjaWZ5aW5nIGludGVnZXJzIFMsIEQsIEwgYW5kIFQgc2VwYXJhdGVkIGJ5IHNpbmdsZSBibGFuayBjaGFyYWN0ZXJzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlMgaXMgdGhlIHNvdXJjZSBjaXR5LCAxJmx0Oz1TJmx0Oz1OPFwvbGk+XHJcblx0PGxpPkQgaXMgdGhlIGRlc3RpbmF0aW9uIGNpdHksIDEmbHQ7PUQmbHQ7PU48XC9saT5cclxuXHQ8bGk+TCBpcyB0aGUgcm9hZCBsZW5ndGgsIDEmbHQ7PUwmbHQ7PTEwMDxcL2xpPlxyXG5cdDxsaT5UIGlzIHRoZSB0b2xsIChleHByZXNzZWQgaW4gdGhlIG51bWJlciBvZiBjb2lucyksIDAmbHQ7PVQmbHQ7PTEwMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdGljZSB0aGF0IGRpZmZlcmVudCByb2FkcyBtYXkgaGF2ZSB0aGUgc2FtZSBzb3VyY2UgYW5kIGRlc3RpbmF0aW9uIGNpdGllcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIHRoZSBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgdG90YWwgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGZyb20gdGhlIGNpdHkgMSB0byB0aGUgY2l0eSBOIHdob3NlIHRvdGFsIHRvbGwgaXMgbGVzcyB0aGFuIG9yIGVxdWFsIEsgY29pbnMuPFwvcD5cclxuXHJcbjxwPklmIHN1Y2ggcGF0aCBkb2VzIG5vdCBleGlzdCwgb25seSBudW1iZXIgLTEgc2hvdWxkIGJlIHdyaXR0ZW4gdG8gdGhlIG91dHB1dCBmaWxlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==