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.*;

public class Main{
	static LinkedList<int[]>adj[],qs[];
	static long[]in,ans;
	static long[]up,down,prefNodes,prefEdges;
	static long[]parEdge;
	static void dfsDown(int i,int p,long val) {
		prefNodes[i]=in[i];
		prefEdges[i]=val;
		parEdge[i]=val;
		if(p!=-1) {
			prefNodes[i]+=prefNodes[p];
			prefEdges[i]+=prefEdges[p];
		}
		for(int[]nxt:adj[i]) {
			if(nxt[0]==p)continue;
			int u=nxt[0];
			long w=nxt[1];
			dfsDown(u, i, w);
			down[i]+=Math.max(0, down[u]+in[u]-w-w);
		}
		
	}
	static void dfsUp(int i,int p) {
		for(int[]nxt:adj[i]) {
			if(nxt[0]==p)continue;
			int u=nxt[0];
			long w=nxt[1];
			long me=down[i]-Math.max(0, down[u]+in[u]-w-w);
			up[u]=Math.max(0, me+in[i]-w-w+up[i]);
			dfsUp(u, i);
		}
	}
	static int log = 22;
	static int[] level, par[];
	static void preLCA(int root,int n) {
		par = new int[n][log];
		level = new int[n];
		dfs(root, root);
	}
 
	static int lca(int u, int v) {
		 
		if (level[u] < level[v])
			return lca(v, u);
		for (int i = log - 1; i >= 0; i--) {
			int u2 = par[u][i];
			if (level[u2] >= level[v])
				u = u2;
		}
		if (u == v)
			return u;
		for (int i = log - 1; i >= 0; i--) {
			int u2 = par[u][i], v2 = par[v][i];
			if (u2 != v2) {
				u = u2;
				v = v2;
			}
		}
		return par[u][0];
	}
	static int lastChild(int u,int grandPar) {
		for (int i = log - 1; i >= 0; i--) {
			int u2 = par[u][i];
			if (level[u2] > level[grandPar])
				u = u2;
		}
		return u;
	}
	static void dfs(int u, int p) {
		par[u][0] = p;
		for (int i = 1; i < log; i++)
			par[u][i] = par[par[u][i - 1]][i - 1];
		for (int[]v : adj[u])
			if (v[0] != p) {
				level[v[0]] = level[u] + 1;
				dfs(v[0], u);
			}
 
	}
	static long[]pref;
	static void lastDfs(int i,int p,long curPref) {
		pref[i]=curPref;
		for(int[]q:qs[i]) {
			int lca=q[0],idx=q[1];
			ans[idx]+=curPref-pref[lca];
		}
		for(int[]nxt:adj[i]) {
			if(nxt[0]==p)continue;
			int u=nxt[0];
			long w=nxt[1];
			lastDfs(u, i, curPref+down[i]-Math.max(0, down[u]+in[u]-w-w));
		}
	}
	static void main() throws Exception{
		int n=sc.nextInt(),q=sc.nextInt();
		in=sc.longArr(n);
		adj=new LinkedList[n];
		qs=new LinkedList[n];
		for(int i=0;i<n;i++) {
			adj[i]=new LinkedList<int[]>();
			qs[i]=new LinkedList<int[]>();
		}
		for(int i=0;i<n-1;i++) {
			int x=sc.nextInt()-1,y=sc.nextInt()-1,w=sc.nextInt();
			adj[x].add(new int[] {y,w});
			adj[y].add(new int[] {x,w});
		}
		ans=new long[q];
		prefNodes=new long[n];
		prefEdges=new long[n];
		down=new long[n];
		up=new long[n];
		parEdge=new long[n];
		dfsDown(0, -1, 0);
		dfsUp(0, -1);
		preLCA(0, n);
		for(int i=0;i<q;i++) {
			int u=sc.nextInt()-1,v=sc.nextInt()-1;
			if(u==v) {
				ans[i]=down[u]+up[u]+in[u];
				continue;
			}
			int lca=lca(u, v);
			ans[i]=up[lca]+prefNodes[u]+prefNodes[v]-prefNodes[lca]*2+in[lca]-(prefEdges[u]+prefEdges[v]-prefEdges[lca]*2);
			if(u!=lca) {
				qs[u].add(new int[] {lca,i});
				ans[i]+=down[u];
			}
			if(v!=lca) {
				qs[v].add(new int[] {lca,i});
				ans[i]+=down[v];
			}
			if(u!=lca && v!=lca) {
				ans[i]-=down[lca];
			}
		}

		pref=new long[n];
		lastDfs(0,-1,0);
		for(int i=0;i<q;i++) {
			pw.println(ans[i]);
		}
    }
    public static void main(String[] args) throws Exception{
    	sc=new MScanner(System.in);
    	pw = new PrintWriter(System.out);
        int tc=1;
//        tc=sc.nextInt();
        for(int i=1;i<=tc;i++) {
//            pw.printf("Case #%d: ", i);
            main();
        }
        pw.flush();
    }
    static PrintWriter pw;
    static MScanner sc;
    static class MScanner {
        StringTokenizer st;
        BufferedReader br;
        public MScanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }
     
        public MScanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }
     
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public int[] intArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public long[] longArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public int[] intSortedArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public long[] longSortedArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public Integer[] IntegerArr(int n) throws IOException {
            Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public Long[] LongArr(int n) throws IOException {
            Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public String nextLine() throws IOException {
            return br.readLine();
        }
     
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
     
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
     
        public char nextChar() throws IOException {
            return next().charAt(0);
        }
     
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
     
        public boolean ready() throws IOException {
            return br.ready();
        }
     
        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }
        
    }
    static void sort(int[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void sort(long[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void shuffle(int[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            int tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
    static void shuffle(long[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            long tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
}