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

---

در کشور اسکاتلند تفاوت‌های چشمگیری در قیمت بنزین دیده می‌شود؛ مثلاً قیمت بنزین در شهر $\text{Dunfermline}$ حدود ۱۳۵.۷ پنس برای هر لیتر است، در حالی که در $\text{Glasgow}$ و $\text{Kilmarnock}$ حدود ۱۳۰.۹ پنس است. مردم اسکاتلند می‌خواهند بدانند برای سفر از هر شهر به شهری دیگر چند پنس باید هزینه کنند. کشور اسکاتلند $n$ شهر و $m$ جاده دارد و بین هر دو شهری حداکثر یک جاده وجود دارد. هر جاده را با سه عدد $v$ و $u$ و $w$ نشان می‌دهیم که نشان دهنده‌ی جاده‌ای بین دو شهر $v$ و $u$ است و عبور از این جاده از هر دو جهت $w$ لیتر بنزین نیاز دارد. همچنین می‌دانیم هر لیتر بنزین در شهر $i$ام $a_i$ پنس قیمت دارد. شما باید به ازای هر دو شهر $s$ و $t$ محاسبه کنید کمترین مقدار پولی که باید خرج کنیم تا از شهر $s$ به شهر $t$ برسیم چند پنس است. دقت کنید که در ابتدا که در شهر $s$ هستیم هیچ بنزینی نداریم و همچنین هر مقدار که بخواهیم می‌توانیم در هر شهر بنزین بزنیم و ظرفیتی روی بنزینی که حمل می‌کنیم نداریم. تنها محدودیت این است که هنگام استفاده از یک جاده باید بنزین مورد نیاز را داشته باشیم.

ورودی

در خط اول ورودی دو عدد $n$ و $m$ تعداد شهر ها و تعداد جاده‌های اسکاتلند می‌آید.

در خط دوم ورودی دنباله‌ی $a_1, a_2, \ldots, a_n \ $ می‌آید که $a_i$ نشان‌دهنده‎‌ی قیمت هر لیتر بنزین در شهر $i$ می‌باشد.

در هر کدام از $m$ خط بعدی سه عدد $v$ و $u$ و $w$ می‌آیند که نشان دهنده‌ی جاده‌ای دوطرفه بین دو شهر $v$ و $u$ است و استفاده از این جاده نیاز به $w$ لیتر بنزین دارد.

$$1 \le n \le 500$$ $$n-1 \le m \le \frac{n(n-1)}{2}$$ $$1 \le v \neq u \le n$$ $$1 \le w, a_i \le 10^6$$

تضمین می‌شود گراف ورودی همبند است و همچنین بین هر دو راس حداکثر یک جاده وجود دارد(جاده تکراری نداریم).

خروجی

خروجی به صورت یک ماتریس $n \times n$ است که خانه‌ی $(i, j)$ آن نشان‌دهنده‌ی کمترین مقدار پول مورد نیاز برای رفتن از شهر $i$ به شهر $j$ می‌باشد.

مثال

ورودی نمونه ۱

3 3
1 10 3
1 2 4
2 3 5
3 1 6

خروجی نمونه ۱

0 4 6
40 0 46
18 15 0

ورودی نمونه ۲

5 7
600783 171847 191295 353053 995582
1 2 479221
1 3 159037
1 4 917731
4 5 63986
5 1 809126
4 2 64758
4 3 880750

خروجی نمونه ۲

0 217642290081 95546725971 228770758107 239766560249
82352691187 0 109682722526 11128468026 22124270168
30422982915 122095564110 0 133224032136 144219834278
105215697361 22863006174 132545728700 0 22590449258
168919007213 86566316026 196249038552 63703309852 0