====== Triangular Graph ======
مثلث خیام-پاسکال را در نظر بگیرید. فرض کنید هر کدام از اعداد این مثلث یک راس از یک گراف هستند. و هر راس (به جز رئوس سطر آخر) به رئوس سطر پایین خود که در سمت راست و چپ آن قرار دارند٬ یال جهت‌دار وزن‌دار دارند. یعنی هر راس دو یال دارد (به جز رئوس 
سطر آخر). 

برنامه‌ای بنویسید که یک گراف با شرایط بالا را از ورودی بگیرد و طول کوتاه‌ترین مسیر از سطر اول به سطر آخر را بیابد. 

===== ورودی ===== 
  * در نخستین سطر ورودی عدد $n$ آمده است. که برابر تعداد سطرهای مثلث است.
  * سپس در $n-1$ سطر وزن یال‌ها به این صورت آمده است که در سطر $i$ام٬ $i$ تا دوتایی به‌صورت $(x,y)$ آمده است که دوتایی $j$ ام در این سطر٬ به ترتیب وزن یال‌های سمت چپ و راست راس $j$ ام در سطر $i$ ام هستند. این دوتایی‌ها با یک فاصله از هم جدا شده اند.
  *  $1 \leq n \leq 1000$
  *  وزن یال‌ها بین $-1000$ تا $1000$ هستند.

===== خروجی =====

در تنها سطر خروجی طول کوتاه‌ترین مسیر از سطر اول به سطر آخر را چاپ کنید.

===== محدودیت‌ها =====

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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|3 \\ (0,-1) \\ (4,-1)  (1,-1)|-2|
</WRAP>


<پاسخ>
منتظر پر کردن این قسمت توسط علاقمندان هستیم.
</پاسخ>

  * [[سوال ۱۸|سوال بعد]]
  * [[سوال ۱۶|سوال قبل]]