+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
در کشور اسکاتلند تفاوت‌های چشمگیری در قیمت بنزین دیده می‌شود؛ مثلاً قیمت بنزین در شهر
$\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
```