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

شما باید برنامه‌ای بنویسید که با دریافت این اطلاعات تعدادی از جاده‌ها را انتخاب کند که شرایط زیر برقرار شود:

• ارتباط جاده‌ای بین همه‌ی شهرها برقرار شود.
• سود خالص یعنی میزان کل سود دهی منهای هزینه‌ی کل ساخت جاده‌ها بیشینه شود.

در سطر اول فایل ورودی به ترتیب $n$ تعداد شهرها و سپس $m$ تعداد جاده‌های قابل ساخت آمده است. شماره‌ی شهرها از ۱ تا $n$‌می‌باشد. در $m$‌ سطر بعد، در هر یک اطلاعات مربوط به یک جاده‌ی قابل ساخت امده است. در هر یک از این سطر‌ها، چهار عدد نوشته شده. دو عدد اول شماره‌ی شهرهایی است که در دو سر این جاده قرار دارد. دو عدد بعد به ترتیب هزینه‌ی ساخت و میزان سود دهی این جاده می‌باشند که هر کدام یک عدد صحیح بین ۰ و $10^5$ می‌باشد.توجه کنید که همیشه این کار ممکن است.($1 \leq n \leq1000$ و $1 \leq m \leq10^5$).

در سطر اول میزان سود خالص و در سطر دوم $p$ تعداد جاده‌هایی را که باید احداث شود، بنویسید. در $p$ سطر بعد در هر سطر دو عدد بنویسید که شماره‌ی شهرهای دو سر جاده‌های مورد نظر هستند..

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

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