Time limit: 1 second Memory limit: 256 megabytes ---------- In Scotland, significant differences are seen in gasoline prices. For example, the price of gasoline in the city of $\text{Dunfermline}$ is about 135.7 pence per liter, while in $\text{Glasgow}$ and $\text{Kilmarnock}$ it is about 130.9 pence. The people of Scotland want to know how many pence they must spend to travel from any city to any other city. Scotland has $n$ cities and $m$ roads, and there is at most one road between any two cities. Each road is represented by three numbers $v$, $u$, and $w$, indicating a road between cities $v$ and $u$, and traversing this road requires $w$ liters of gasoline in either direction. We also know that each liter of gasoline in city $i$ costs $a_i$ pence. You must calculate the minimum amount of money (in pence) required to travel from city $s$ to city $t$ for every pair of cities $s$ and $t$. Note that when starting in city $s$, we have no fuel, and we can refuel any amount we desire in any city, with no capacity limit on the fuel we carry. The only restriction is that we must have the required fuel when using a road. # Input The first line of input contains two numbers, $n$ and $m$, the number of cities and the number of roads in Scotland. The second line of input contains the sequence $a_1, a_2, \ldots, a_n \ $, where $a_i$ represents the price per liter of gasoline in city $i$. Each of the following $m$ lines contains three numbers $v$, $u$, and $w$, indicating a bidirectional road between cities $v$ and $u$, requiring $w$ liters of gasoline to use. $$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$$ It is guaranteed that the input graph is connected, and there is at most one road between any two vertices (no duplicate roads). # Output The output is an $n \times m$ matrix where entry $(i, j)$ represents the minimum amount of money required to travel from city $i$ to city $j$. # Example ## Sample Input 1 ``` 3 3 1 10 3 1 2 4 2 3 5 3 1 6 ``` ## Sample Output 1 ``` 0 4 6 40 0 46 18 15 0 ``` ## Sample Input 2 ``` 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 ``` ## Sample Output 2 ``` 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 ```