پس از چنگ چهانی هشت‌ام که در سیاره‌ی مریخ برگزار شد، دزدان دریایی موفق شدند کشور افسانه‌ای ساکارا را تصاحب کنند و رئیس دزدان دریایی، حاکم این کشور شد. او شهر معروف شیویک را به پایتختی خود برگزید.

ساکارا $n$ شهر مختلف که برخی از آن‌ها با جاده‌های یک‌طرفه به یک‌دیگر متصل شده‌اند تشکیل شده است. شهرهای ساکارا با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند. رئیس دزدان دریایی برای اینکه کنترل اوضاع کشور جدیدش را در دست داشته باشد در هر یک از جاده‌های ساکارا تعدادی دزد دریایی قرار داده است. این دزدان برای تامین مخارج خود از گروه‌هایی که از جاده‌ی تحت تسلط آن‌ها عبور می‌کنند مبلغی به زور می‌گیرد. هر دزد به ازای هر بار عبور دقیقا $1$ تومان از گروه جوینده زورگیری می‌کند.

گروهی از جویندگان طلا که در شهر شیویک ساکن هستند، اخیرا دستگاهی ساخته‌اند که به طور شگفت آوری خاک جاده‌های ساکارا را به طلا تبدیل می‌کند. آن‌ها دریافتند که به ازای هر بار عبور، با دستگاه خود، از جاده‌ی $i$ام ساکارا، $p_i$ تومان سود می‌کنند؛ اما مشکل این است که پس از عبور از بعضی شهرها به دوری وارد شوند و سپس تا ابد در این دور حرکت کنند.

آن‌ها فقط درصورتی در ساکارا مشغول به کار می‌شوند که مطمئن باشند که تا انتهای زندگی‌شان سود می‌کنند؛ به عبارت دیگر، مقدار پولی که با دستگاه خود در مجموع دور به دست می‌آورند، بیش‌تر از پولی باشد که مجموعا دزدان دور از آن‌ها می‌گیرند (میزان سود یا زیان در قطعه ابتدایی مسیر برای رسیدن به دور اهمیتی ندارد).

از طرفی حاکم ساکارا دوست دارد که جویندگان طلا در جاده‌های کشورش با دستگاه‌شان مسغول به کار شوند. زیرا از این طریق نیروهای تحت تسلط وی (یعنی همان دزدان میان راه) می‌توانند پول بیش‌تری بگیرند و به فکر شورش نمی‌افتند. او برای این کار حاضر است از تعدادی از جاده‌های کشورش، از هر کدام به میزان حداکثر $t \geq 0$ دزد کم کند به طوری که حداقل یک مسیر مناسب برای جویندگان طلا وجود داشته باشد (واضح است تعداد دزدان هیچ جاده‌ای نیاید منفی شود). البته او می‌خواهد که کم‌ترین حذف ممکن را انجام دهد، تا سود دزدانش هم کم نباشد. برای همین از ما کمک خواسته که برای او برنامه‌ای بنویسیم که کم‌ترین $t$ را برای او بیابد؛ ما هم به شرطی که مسئله‌ی او بی‌جواب نباشد، قبول کرده‌ایم که این کار را بکنیم.

• در سطر اول ورودی، به ترتیب تعداد شهرهای ساکارا ($n$) و تعداد جاده‌های ساکارا ($e$) با یک فاصله از یک‌دیگر آمده‌اند.
• در سطر $i$ از $e$ سطر بعد، به ترتیب چهار عدد صحیح $u$، $v$، $p_i$ و $k_i$ با یک فاصله از هم آمده‌اند که نشان دهنده‌ی این هستند که از شهر $u$ جاده‌ای یک‌طرفه به شهر $v$ وجود دارد که مقدار سودی که در هر بار عبور جویندگان طلا از این جاده حاصل می شود $p_i$ است و $k_i$ دزد دریایی هم در این جاده وجود دارند.
• $1 \leq n \leq 100$ و $1 \leq e \leq 1000$
• دو محدودیت دیگر $0\leq p_i \leq 100,000$ و $0 \leq k_i \leq 100,000$ نیز متصور است.
• ورودی طوری است که حتما جواب وجود دارد.

در تنها سطر خروجی، کوجک‌‌ترین مقدر $t$ را بدهید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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