Meeting on the Scenic Tree

You are given a tree with \( n \) nodes (scenic spots). Each node \( i \) has an integer score \( s_i \). The tree has exactly \( n-1 \) edges, each representing a bidirectional bus route with a toll cost \( w_i \). Although the tolls are given, they are only a distraction in this problem.

There are two travelers: Little Bear starts at node \( a \) and Commander starts at node \( b \). They must meet at some node \( p \) on the unique simple path from \( a \) to \( b \) (i.e. \( p \) is on the path from \( a \) to \( b \)). After meeting, they travel together along a simple path from \( p \) to an arbitrary node \( q \). Note that neither traveler visits the meeting point \( p \) twice.

The toll cost incurred is computed as follows:

• Little Bear pays for the path from \( a \) to \( p \) and then from \( p \) to \( q \).
• Commander pays for the path from \( b \) to \( p \) and then from \( p \) to \( q \).

Because the simple path from \( a \) to \( b \) is unique, for any \( p \) on this path the sum \( d(a,p)+d(b,p)=d(a,b) \) (where \( d(x,y) \) is the sum of toll costs along the unique path between \( x \) and \( y \)). Also, throughout the journey, if an edge is traversed more than once the toll is paid each time, and similarly the scores for scenic spots are added each time they are visited.

The travelers want to minimize the total toll cost and, among all such choices, maximize the sum of the scenic spot scores they collect. They collect scores as follows:

• Little Bear collects the scores of all nodes on his path from \( a \) to \( p \).
• Commander collects the scores of all nodes on his path from \( b \) to \( p \).
• Note that the meeting point \( p \) is counted in both paths.

Thus, if the path from \( a \) to \( b \) is denoted by \( a = v_0, v_1, \dots, v_k = b \) and if they meet at \( p = v_i \), then the total scenic score is:

[ \text{score} = \left(\sum_{j=0}^{i} s_{v_j}\right) + \left(\sum_{j=i}^{k} s_{v_j}\right) = \left(\sum_{j=0}^{k} s_{v_j}\right) + s_{v_i}. ]

Since \( d(a,p)+d(b,p)=d(a,b) \) is independent of the choice of \( p \) on the \( a\to b \) path, the toll cost is minimized by choosing \( q=p \) (so that the extra cost 2\( d(p,q) \) is zero). Therefore, the optimal solution is to choose a meeting point \( p \) on the path from \( a \) to \( b \) such that \( s_{p} \) is maximized. The answer for a query is then:

[ \text{Answer} = \left( \sum_{v \in \text{path}(a, b)} s_v \right) + \max_{v \in \text{path}(a, b)} s_v. ]

You are given \( m \) queries. For each query, given nodes \( a \) and \( b \), output the maximum total scenic score achievable as described above.

inputFormat

The first line contains two integers \( n \) and \( m \), denoting the number of nodes and the number of queries.

The second line contains \( n \) integers: \( s_1, s_2, \ldots, s_n \) where \( s_i \) is the score of node \( i \).

The following \( n-1 \) lines each contain three integers \( u \), \( v \), and \( w \), indicating there is an edge between nodes \( u \) and \( v \) with toll cost \( w \).

The next \( m \) lines each contain two integers \( a \) and \( b \), representing a query.

outputFormat

For each query, output a single integer: the maximum total scenic score under the minimum toll cost strategy. Each answer should be printed on its own line.

sample

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

9
19
17

</p>