Problem: You are given a weighted tree (undirected connected graph with no cycles, loops or multiple edges) with n vertices. The edge \\{u_j, v_j\} has weight w_j. Also each vertex i has its own value a_i assigned to it.

Let's call a path starting in vertex u and ending in vertex v, where each edge can appear no more than twice (regardless of direction), a 2-path. Vertices can appear in the 2-path multiple times (even start and end vertices).

For some 2-path p profit Pr(p) = ∑_{v ∈ distinct vertices in  p}{a_v} - ∑_{e ∈ distinct edges in  p}{k_e ⋅ w_e}, where k_e is the number of times edge e appears in p. That is, vertices are counted once, but edges are counted the number of times they appear in p.

You are about to answer m queries. Each query is a pair of vertices (qu, qv). For each query find 2-path p from qu to qv with maximal profit Pr(p).

Input

The first line contains two integers n and q (2 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ q ≤ 4 ⋅ 10^5) — the number of vertices in the tree and the number of queries.

The second line contains n space-separated integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the values of the vertices.

Next n - 1 lines contain descriptions of edges: each line contains three space separated integers u_i, v_i and w_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^9) — there is edge \\{u_i, v_i\} with weight w_i in the tree.

Next q lines contain queries (one per line). Each query contains two integers qu_i and qv_i (1 ≤ qu_i, qv_i ≤ n) — endpoints of the 2-path you need to find.

Output

For each query print one integer per line — maximal profit Pr(p) of the some 2-path p with the corresponding endpoints.

Example

Input

7 6
6 5 5 3 2 1 2
1 2 2
2 3 2
2 4 1
4 5 1
6 4 2
7 3 25
1 1
4 4
5 6
6 4
3 4
3 7


Output

9
9
9
8
12
-14

Note

Explanation of queries: 

  1. (1, 1) — one of the optimal 2-paths is the following: 1 → 2 → 4 → 5 → 4 → 2 → 3 → 2 → 1. Pr(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 ⋅ w(1,2) + 2 ⋅ w(2,3) + 2 ⋅ w(2,4) + 2 ⋅ w(4,5)) = 21 - 2 ⋅ 12 = 9. 
  2. (4, 4): 4 → 2 → 1 → 2 → 3 → 2 → 4. Pr(p) = (a_1 + a_2 + a_3 + a_4) - 2 ⋅ (w(1,2) + w(2,3) + w(2,4)) = 19 - 2 ⋅ 10 = 9. 
  3. (5, 6): 5 → 4 → 2 → 3 → 2 → 1 → 2 → 4 → 6. 
  4. (6, 4): 6 → 4 → 2 → 1 → 2 → 3 → 2 → 4. 
  5. (3, 4): 3 → 2 → 1 → 2 → 4. 
  6. (3, 7): 3 → 2 → 1 → 2 → 4 → 5 → 4 → 2 → 3 → 7. 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }
    BufferedReader reader;
    BufferedWriter writer;
    StringTokenizer tokenizer;
    public Main() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new BufferedWriter(new OutputStreamWriter(System.out));
    }
    int ni() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {}
        }
        return Integer.parseInt(tokenizer.nextToken());
    }


    int n, q, vws[], intime[], outtime[], time = -1, parents[][], logN = 19, parentIndex[];
    long ps[], answers[], bit[];
    ArrayList<Integer>[] t, tw;
    ArrayList<Long>[] tp;
    ArrayList<Query>[] queries;
    int[] depths;
    void solve() {
        n = ni();
        q = ni();

        vws = new int[n];
        for (int i = 0; i < n; i++) {
            vws[i] = ni();
        }
        t = new ArrayList[n];
        tw = new ArrayList[n];
        tp = new ArrayList[n];
        depths = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = new ArrayList<Integer>();
            tw[i] = new ArrayList<Integer>();
            tp[i] = new ArrayList<Long>();
        }
        for (int i = 0; i < n - 1; i++) {
            int from = ni() - 1;
            int to = ni() - 1;
            int w = ni();
            t[from].add(to);
            tw[from].add(w);
            t[to].add(from);
            tw[to].add(w);
        }
        intime = new int[n];
        outtime = new int[n];
        ps = new long[n];
        parents = new int[n][logN];
        parentIndex = new int[n];
        ps[0] = calcRoot(0, 0, 0);
        calcOthers(0, -1, 0);
//        for (int i = 0; i < n; i++) {
//            System.out.println(ps[i]);
//            for (int j = 0; j < tp[i].size(); j++) {
//                System.out.print(t[i].get(j) + 1 + "->" + tp[i].get(j) + "; ");
//            }
//            System.out.println();
//        }
//        System.out.println();

        answers = new long[q];
        queries = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            queries[i] = new ArrayList<>();
        }
        for (int i = 0; i < q; i++) {
            int u = ni() - 1;
            int v = ni() - 1;
            int parent = lca(u, v);
//            System.out.println(parent);
//            System.out.println(depths[parent]);
            Query q = new Query(i, depths[parent]);
            queries[u].add(q);
            queries[v].add(q);
            answers[i] = - ps[parent] + (parent != 0 ? tp[parent].get(parentIndex[parent]) * 2 : 0);
        }

        bit = new long[n];
        calcAnswers(0, 0);

        try {
            for (int i = 0; i < q; i++) {
                writer.write(answers[i] + "\n");
            }
            writer.close();
        } catch (IOException e) {}
    }

    long calcRoot(int v, int p, int d) {
        intime[v] = ++time;
        depths[v] = d;
        parents[v][0] = p;
        for (int i = 1; i < logN; i++) {
            parents[v][i] = parents[parents[v][i - 1]][i - 1];
        }
        long cost = vws[v];
        for (int i = 0; i < t[v].size(); i++) {
            int ch = t[v].get(i);
            if (ch != p) {
                long ew = Math.max(0, calcRoot(ch, v, d + 1) - 2 * tw[v].get(i));
                tp[v].add(ew);
                cost += ew;
            } else {
                tp[v].add(0L);
            }
        }
        outtime[v] = ++time;
        return cost;
    }
    void calcOthers(int v, int p, long c) {
        long curCost = c + vws[v];
        for (int i = 0; i < t[v].size(); i++) {
            int ch = t[v].get(i);
            if (ch == p) {
                tp[v].set(i, (long)c);
                parentIndex[v] = i;
            } else {
                curCost += tp[v].get(i);
            }
        }
        ps[v] = curCost;
        for (int i = 0; i < t[v].size(); i++) {
            int ch = t[v].get(i);
            if (ch != p) {
                calcOthers(ch, v, Math.max(0, curCost - tp[v].get(i) - tw[v].get(i) * 2));
            }
        }
    }
    boolean isParent(int p, int v) {
        return intime[p] <= intime[v] && outtime[p] >= outtime[v];
    }
    int lca(int u, int v) {
        if (isParent(u, v)) return u;
        if (isParent(v, u)) return v;
        for (int i = logN - 1; i >=0; i--) {
            if (!isParent(parents[v][i], u)) {
                v = parents[v][i];
            }
        }
        return parents[v][0];
    }

    void set(int i, long dif) {
        while (i < n) {
            bit[i] += dif;
            i = i | (i + 1);
        }
    }
    long get(int i, int j) {
        return sum(j) - sum(i - 1);
    }
    long sum(int i) {
        long res = 0;
        while (i >= 0) {
            res += bit[i];
            i = (i & (i + 1)) - 1;
        }
        return res;
    }

    void calcAnswers(int v, int p) {
        long cur = ps[v];
        if (p != v) {
            cur -= tp[v].get(parentIndex[v]);
        }
        for (Query q : queries[v]) {
            answers[q.i] += cur + get(q.d, depths[v] - 1);
        }
        set(depths[v], cur);
        for (int i = 0; i < t[v].size(); i++) {
            if (t[v].get(i) == p) {
                continue;
            }
            long curSub = tp[v].get(i) + tw[v].get(i);
            set(depths[v], -curSub);
            calcAnswers(t[v].get(i), v);
            set(depths[v], curSub);
        }
        set(depths[v], -cur);
    }

}

class Query {
    public int i;
    public int d;
    public Query(int index, int depth) {
        i = index;
        d = depth;
    }
}