در کشور ایران $N$ شهر به نام‌های $1...N$ وجود دارد که با جاده‌های یک طرفه به هم مربوطند. به هر جاده دو عدد نسبت داده شده است. طول جاده و مقدار پولی که باید برای عبور از آن بپردازیم.

هادی که برای یک جلسه به اهواز رفته بود می‌خواهد خود را هرچه سریع‌تر به تهران برساند. چون باید سر جلسه‌ی کمیته‌ی کامپیوتر حاضر شود. ولی متاسفانه فقط $k$ تومان پول دارد.

از شما می‌خواهیم که به او کمک کنید. کوتاه‌ترین مسیری را بیابید که هادی با استفاده از آن به تهران برسد. (در واقع هزینه‌ی این مسیر نباید بیش‌تر از $k$ تومان باشد.)

در سطر اول فایل ورودی عدد $k$ در سطر دوم عدد $N$ و در سطر سوم عدد $R$ تعداد جاده‌ها داده شده است. دقت کنید $0\leq k \leq 10^4$ و $2\leq N \leq 100$ و $1\leq R \leq 10^4$.

در $R$ سطر بعدی در هر سطر یک جاده داده با چهار عدد $S,D,L,T$ مشخص شده است. $S$ شهر شروع جاده، $D$‌ شهر پایان آن، $L$ شهر طول جاده و $T$ هزینه‌ی عبور از آن برحسب تومان هستند. دقت کنید $1 \leq L \leq 100$ و $0\leq T \leq 100$. فرض کنید اهواز (مکان شروع هادی) شهر ۱ و تهران (مقصد هادی) شهر $N$ است.

در تنها سطر فایل خروجی شما باید طول کوتاه‌ترین مسیر از شهر ۱ به $N$ که هزینه‌ی استفاده از آن حداکثر $k$ باشد را بنویسید. اگر چنین مسیری وجود نداشت عدد ۱- را در خروجی بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۶۰۰ کیلوبایت

• سوال بعد
• سوال قبل