Миле се наоѓа на привремен престој во една далечна земја во Европа. Во моментот кога разбрал дека во градот во кој се наоѓал се појавил заразен пациент од вирусот К, тој дигнал паника и под итно решил да си оди дома. Но, во себе има само S евра. Затоа тој ги разгледал цените на многу евтини летови од одреден до одреден град во Европа, па со комбинирање на некои од нив се надева дека за парите што ги има ќе успее да стигне дома.

Нека го означиме со 1 градот во кој тој се наоѓа, со N – неговиот роден град (кај што треба да стигне), а со 2, 3, …, N – 1 − останатите градови преку кои може да патува. Тој направил листа од M можности за патување од тип: авион од град v до град w (се разбира, и во обратната насока: w до v) патува t временски единици и билетот во секоја од двете насоки чини e евра. Можно е да има повеќе од еден авион, кој патува меѓу v и w и може различните авиони (од различни нискобуџетни компании, на пример), кои патуваат од v до w да патуваат различно време и цената на билетите да им е различна.

Напишете програма која наоѓа патување од градот 1 до градот N по цена која не надминува S евра. Ако има повеќе од едно такво патување, програмата треба да го најде патувањето, при кое Миле ќе помине најмалку време во авион и со тоа ќе му се сведе на минимум паниката дека ќе се зарази од некој од другите патници.

Влез

Во првиот ред се дадени позитивните цели броеви S, N и M (S ≤ 2000, 2 ≤ N ≤ 3000, M ≤ 5000). Во секој од следните M реда се дадени параметрите (позитивни цели броеви) v, w, t и e на еден можен авионски лет, 1 ≤ v ≤ N, 1 ≤ w ≤ N, 1 ≤ t ≤ 100, 1 ≤ e ≤ 100.

Излез

Програмата треба да го испише времето кое Миле ќе го помине во авиони. Ако нема патување со цена која не надминува S евра, програмата треба да испише –1.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
7 4 6
1 2 2 5
1 3 2 2
1 4 7 3
2 3 1 2
2 4 2 3
3 4 5 2

излез
5

влез
4 4 6
1 2 2 5
1 3 2 2
1 4 7 5
2 3 1 2
2 4 2 3
3 4 5 3

излез
-1