Problem
اعلیحضرت پادشاه Bubei II مایل بود به اطراف قلمرو خود سفر کند. در عین حال، مسیر دارای خواسته های زیر است:
1) مسیر باید کمترین زمان ممکن را طی کند (زمان سلطنتی – چیز بسیار ارزشمندی است و باید محافظت شود)؛
2) مسیر باید دقیقاً یک بار شامل همه سکونتگاه ها باشد (اگر پادشاه یک شهرک را از دست بدهد، ساکنان آن از بی توجهی سلطنتی خشمگین می شوند و مالیات پرداخت نمی کنند؛ اگر پادشاه بیش از یک بار از یک سکونتگاه بازدید کند، ساکنان بقیه شهرک ها خشمگین می شوند. اقلام شهرک سازی نیز خشمگین خواهند شد)
3) مسیر باید در پایتخت ایالت شروع و به پایان برسد (پادشاه پس از گردش در اموال خود باید فوراً دست به کار شود). پایتخت دقیقاً 2 بار در مسیر قرار می گیرد: به عنوان مبدأ و به عنوان مقصد نمی تواند یک استقرار میانی مسیر باشد.
برنامه ای بنویسید که از نقشه راه پادشاهی برای یافتن چنین مسیری استفاده کند یا تعیین کند که انجام همه الزامات غیرممکن است.
ورودی
ابتدا عدد N را وارد کنید (طبیعی، از 10 تجاوز نمی کند) – تعداد سکونتگاه های پادشاهی سپس N خط از N عدد در هر – زمان سفر بین شهرک ها (زمان – یک عدد صحیح غیر منفی است، از 500 تجاوز نمی کند؛ اگر زمان = 0 باشد، به این معنی است که بین برخی از تسویه ها راهی وجود ندارد). شهرک شماره 1 پایتخت ایالت است.
حصر
حداقل زمانی را که اعلیحضرت برای انحراف در دامنه‌های خود صرف می‌کنند، یا اگر امکان ساخت مسیر با ویژگی‌های داده شده غیرممکن باشد، عدد -1 را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |