#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool upmin(T &x, T y) {
  return y <= x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x <= y ? x = y, 1 : 0;
}
const long double eps = 1e-9;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = (1ll << 62) - 1;
const int MAXN = 600005;
const int mods = 998244353;
const int MX = 100000;
const int inv2 = (mods + 1) >> 1;
const int INF = 0x3f3f3f3f;
namespace FastIO {
constexpr int SIZE = (1 << 21) + 1;
int num = 0, f;
char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf,
                                                *oT = obuf + SIZE - 1, c;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void getc(char &c) {
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       !isalpha(c) && c != EOF;
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
}
inline void reads(char *st) {
  char c;
  int n = 0;
  getc(st[++n]);
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       isalpha(c);
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    st[++n] = c;
  st[++n] = '\0';
}
template <class I>
inline void read(I &x) {
  for (f = 1, c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = (x << 3) + (x << 1) + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (x < 0) putc('-'), x = -x;
  if (!x) putc('0');
  while (x) que[++num] = x % 10 + 48, x /= 10;
  while (num) putc(que[num--]);
}
inline void putstr(string st) {
  for (int i = 0; i < (int)st.size(); ++i) putc(st[i]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_Flusher_;
}  // namespace FastIO
using FastIO ::print;
using FastIO ::putc;
using FastIO ::putstr;
using FastIO ::read;
using FastIO ::reads;
struct enode {
  int nxt, to, c;
} e[MAXN << 1];
int head[MAXN], C[MAXN], fa[MAXN][20], dep[MAXN], a[MAXN], Log[MAXN],
    edgenum = 0;
long long f[MAXN], g[MAXN], h[MAXN], sum[MAXN][20];
void add(int u, int v, int c) {
  e[++edgenum] = (enode){head[u], v, c}, head[u] = edgenum;
}
void tree_dp(int x, int father) {
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == father) continue;
    tree_dp(v, x);
  }
  f[x] = a[x];
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to, c = e[i].c;
    if (v == father) continue;
    f[x] += max(f[v] - c - c, 0ll);
  }
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to, c = e[i].c;
    if (v == father) continue;
    g[v] = f[x] - max(f[v] - c - c, 0ll);
  }
}
void dfs(int x, int father) {
  dep[x] = dep[father] + 1, fa[x][0] = father, sum[x][0] = g[x] - C[x];
  for (int i = 1; i <= Log[dep[x]]; ++i)
    fa[x][i] = fa[fa[x][i - 1]][i - 1],
    sum[x][i] = sum[x][i - 1] + sum[fa[x][i - 1]][i - 1];
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to, c = e[i].c;
    if (v == father) continue;
    h[v] = max(h[x] + f[x] - max(f[v] - c - c, 0ll) - c - c, 0ll);
    C[v] = c;
    dfs(v, x);
  }
}
int getlca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = Log[dep[x]]; i >= 0; --i)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  if (x == y) return x;
  for (int i = Log[dep[x]]; i >= 0; --i)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
int jump(int u, int d) {
  for (int i = Log[d]; i >= 0; --i)
    if ((d >> i) & 1) u = fa[u][i];
  return u;
}
long long getsum(int u, int d) {
  long long ans = 0;
  for (int i = Log[d]; i >= 0; --i)
    if ((d >> i) & 1) ans += sum[u][i], u = fa[u][i];
  return ans;
}
signed main() {
  int n, Case;
  read(n), read(Case);
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1, u, v, c; i < n; ++i)
    read(u), read(v), read(c), add(u, v, c), add(v, u, c);
  tree_dp(1, 0);
  dep[0] = -1, Log[1] = 0;
  for (int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  dfs(1, 0);
  while (Case--) {
    int u, v;
    read(u), read(v);
    if (dep[u] < dep[v]) swap(u, v);
    long long ans = 0;
    int t = getlca(u, v);
    if (u == v)
      ans = h[u] + f[u];
    else if (v == t) {
      int uu = jump(u, dep[u] - dep[t] - 1);
      ans = h[t] + f[t] - max(f[uu] - C[uu] - C[uu], 0ll) +
            getsum(u, dep[u] - dep[t] - 1) + f[u] - C[uu];
    } else {
      int uu = jump(u, dep[u] - dep[t] - 1), vv = jump(v, dep[v] - dep[t] - 1);
      ans = h[t] + f[t] - max(f[uu] - C[uu] - C[uu], 0ll) -
            max(f[vv] - C[vv] - C[vv], 0ll) - C[uu] - C[vv];
      ans += getsum(u, dep[u] - dep[t] - 1) + getsum(v, dep[v] - dep[t] - 1) +
             f[u] + f[v];
    }
    print(ans), putc('\n');
  }
  return 0;
}

### Prompt

In cpp, your task is to solve the following 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. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool upmin(T &x, T y) {
  return y <= x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x <= y ? x = y, 1 : 0;
}
const long double eps = 1e-9;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = (1ll << 62) - 1;
const int MAXN = 600005;
const int mods = 998244353;
const int MX = 100000;
const int inv2 = (mods + 1) >> 1;
const int INF = 0x3f3f3f3f;
namespace FastIO {
constexpr int SIZE = (1 << 21) + 1;
int num = 0, f;
char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf,
                                                *oT = obuf + SIZE - 1, c;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void getc(char &c) {
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       !isalpha(c) && c != EOF;
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
}
inline void reads(char *st) {
  char c;
  int n = 0;
  getc(st[++n]);
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       isalpha(c);
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    st[++n] = c;
  st[++n] = '\0';
}
template <class I>
inline void read(I &x) {
  for (f = 1, c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = (x << 3) + (x << 1) + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (x < 0) putc('-'), x = -x;
  if (!x) putc('0');
  while (x) que[++num] = x % 10 + 48, x /= 10;
  while (num) putc(que[num--]);
}
inline void putstr(string st) {
  for (int i = 0; i < (int)st.size(); ++i) putc(st[i]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_Flusher_;
}  // namespace FastIO
using FastIO ::print;
using FastIO ::putc;
using FastIO ::putstr;
using FastIO ::read;
using FastIO ::reads;
struct enode {
  int nxt, to, c;
} e[MAXN << 1];
int head[MAXN], C[MAXN], fa[MAXN][20], dep[MAXN], a[MAXN], Log[MAXN],
    edgenum = 0;
long long f[MAXN], g[MAXN], h[MAXN], sum[MAXN][20];
void add(int u, int v, int c) {
  e[++edgenum] = (enode){head[u], v, c}, head[u] = edgenum;
}
void tree_dp(int x, int father) {
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == father) continue;
    tree_dp(v, x);
  }
  f[x] = a[x];
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to, c = e[i].c;
    if (v == father) continue;
    f[x] += max(f[v] - c - c, 0ll);
  }
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to, c = e[i].c;
    if (v == father) continue;
    g[v] = f[x] - max(f[v] - c - c, 0ll);
  }
}
void dfs(int x, int father) {
  dep[x] = dep[father] + 1, fa[x][0] = father, sum[x][0] = g[x] - C[x];
  for (int i = 1; i <= Log[dep[x]]; ++i)
    fa[x][i] = fa[fa[x][i - 1]][i - 1],
    sum[x][i] = sum[x][i - 1] + sum[fa[x][i - 1]][i - 1];
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].to, c = e[i].c;
    if (v == father) continue;
    h[v] = max(h[x] + f[x] - max(f[v] - c - c, 0ll) - c - c, 0ll);
    C[v] = c;
    dfs(v, x);
  }
}
int getlca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = Log[dep[x]]; i >= 0; --i)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  if (x == y) return x;
  for (int i = Log[dep[x]]; i >= 0; --i)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
int jump(int u, int d) {
  for (int i = Log[d]; i >= 0; --i)
    if ((d >> i) & 1) u = fa[u][i];
  return u;
}
long long getsum(int u, int d) {
  long long ans = 0;
  for (int i = Log[d]; i >= 0; --i)
    if ((d >> i) & 1) ans += sum[u][i], u = fa[u][i];
  return ans;
}
signed main() {
  int n, Case;
  read(n), read(Case);
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1, u, v, c; i < n; ++i)
    read(u), read(v), read(c), add(u, v, c), add(v, u, c);
  tree_dp(1, 0);
  dep[0] = -1, Log[1] = 0;
  for (int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  dfs(1, 0);
  while (Case--) {
    int u, v;
    read(u), read(v);
    if (dep[u] < dep[v]) swap(u, v);
    long long ans = 0;
    int t = getlca(u, v);
    if (u == v)
      ans = h[u] + f[u];
    else if (v == t) {
      int uu = jump(u, dep[u] - dep[t] - 1);
      ans = h[t] + f[t] - max(f[uu] - C[uu] - C[uu], 0ll) +
            getsum(u, dep[u] - dep[t] - 1) + f[u] - C[uu];
    } else {
      int uu = jump(u, dep[u] - dep[t] - 1), vv = jump(v, dep[v] - dep[t] - 1);
      ans = h[t] + f[t] - max(f[uu] - C[uu] - C[uu], 0ll) -
            max(f[vv] - C[vv] - C[vv], 0ll) - C[uu] - C[vv];
      ans += getsum(u, dep[u] - dep[t] - 1) + getsum(v, dep[v] - dep[t] - 1) +
             f[u] + f[v];
    }
    print(ans), putc('\n');
  }
  return 0;
}

```