Cowpaths Toll

FJ has set up tolls on both cowpaths (edges) and pastures (nodes) throughout his farm.

The farm is modeled as an undirected graph with $n$ vertices and $m$ edges. Each edge connects two different vertices and has an associated toll $w_i$. In addition, every vertex has a toll $c_i$. A cow traveling along a path pays the sum of the tolls of all edges traversed plus a single extra toll equal to the maximum of the tolls of all the vertices visited (including the start and end vertices).

The cost of a path $P$ is defined as follows:
$$ \text{cost}(P)=\left(\sum_{(u,v)\in P}w_{uv}\right)+\max_{v\in P}c_v.

$$

You are given $q$ queries. Each query specifies a starting vertex $s$ and an ending vertex $t$, and your task is to determine the minimum cost to travel from $s$ to $t$. ## inputFormat The input begins with a line containing two integers $n$ and $m$ ($1\le n\le 250$, $1\le m\le 10^4$), representing the number of vertices and edges respectively.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1\le c_i\le 10^5$), where $c_i$ denotes the toll of vertex $i$.

Then follow $m$ lines, each containing three integers $u_i$, $v_i$, and $w_i$ ($1\le u_i,v_i\le n$, $u_i\neq v_i$, $1\le w_i\le 10^5$). Each of these lines indicates that vertices $u_i$ and $v_i$ are connected by a bidirectional edge with toll $w_i$. Note that there may be multiple edges between the same pair of vertices, but there are no self-loops. It is guaranteed that there is a path between any two vertices.

The next line contains a single integer $q$ ($1\le q\le 10^4$), representing the number of queries.

Each of the following $q$ lines contains two integers $s_i$ and $t_i$ ($1\le s_i,t_i\le n$, $s_i\neq t_i$), representing a query for the minimum cost path from vertex $s_i$ to vertex $t_i$. ## outputFormat For each query, output a single line containing one integer — the minimum cost to travel from the starting vertex to the destination vertex, computed as the sum of the tolls of the traversed edges plus the maximum vertex toll encountered along the path. ## sample

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

7
7
8

$$