در یک کشور $n$ شهر وجود دارد. بین این شهرها تعدادی لوله کشیده شده است. هر کدام از این لوله‌ها طولی خاص خود دارند. در این کشور هر کدام از شهرهای $s$ و $t$ دارای منبع بزرگ هستند. در منبع شهر $s$، $x$ لیتر آب وجود دارد و در منبع شهر $t$، $y$ لیتر آب. لوله‌ها به نحوی کشیده شده‌اند که آب هر منبع می‌تواند به هر شهری برسد. شهر $i$ام این کشور به $f_i$ لیتر آب نیاز دارد (خود شهرهای $s$ و $t$ هم به $f_s$ و $f_t$ لیتر آب نیاز دارند). در ضمن می‌دانیم:

$$\sum_{i=1}^n f_i=x+y$$

حال می‌خواهیم آب منابع را در این لوله‌ها طوری بفرستیم که به هر شهر مقدار آبی که نیاز دارد برسد (ممکن است از بعضی از لوله‌ها آب عبور نکند). می‌دانیم هزینه‌ی گذراندن هر لیتر آب از یک لوله برابر طول آن است.

برنامه‌ای بنویسید که:

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

در سطر اول ورودی، به ترتیب $n$، $e$(تعداد لوله‌ها)، $t،x،s$ و $y$ قرار گرفته است.($2\leq n \leq 5000$ و $n-1\leq e \leq 400000$ )

در سطر دوم، $n$ عدد $f_n،…،f_2،f_1$ نوشته شده است.($0\leq f_i 10^5$)

در هر یک از $e$ سطر بعد، سه عدد $v،u$ و $c$ نوشته شده که نشان‌دهنده‌ی لوله‌ای به طول $c$ بین شهر‌های $u$ و $v$ است.

اعداد هر سطر با فاصله از هم جدا شده‌اند.

طول لوله‌ها حداقل ۱ و حداکثر $10^5$ است و همه‌‌ی لوله‌های دنیا دو طرفه هستند!!!

بین هر دو شهر حداکثر یک لوله وجود دارد.

تمام اعداد ورودی صحیح و نامنفی هستند.

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

در سطرهای بعدی لوله‌هایی که از آن‌ها مقدار ناصفری آب می‌گذرد را بنویسید؛ به این ترتیب که اگر $l$ لیتر آب از شهر $u$ به $v$ می‌رود شما باید به ترتیب $v،u$ و $l$ را در یک سطر بنویسید. ترتیب نوشتن لوله‌ها اهمیتی ندارد.

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

• سوال قبل