中样例过了，1-8全WA

#include <bits/stdc++.h>

constexpr auto maxn = 2050;

class edge
{
public:
	int to;
	int next;
    int dis;
};

class node
{
public:
    int idx;
    long long dis;

    bool operator>(node const& other) const
    {
        return other.dis > this->dis;
    }
};

edge edges[maxn * 2];
int  heads[maxn];
bool visited[maxn];
long long dis[maxn][maxn];

int n, q, c[maxn], u, v, w, x, y;

auto cnt = 0;
void add(int u, int v, int w)
{
    edges[++cnt].to = v;
    edges[cnt].next = heads[u];
    edges[cnt].dis  = w;
    heads[u]        = cnt;
}

void dijkstra(int start)
{
    std::priority_queue<node, std::vector<node>, std::greater<node>> q;

    dis[start][start] = 0;
    q.push(node{start, 0});
    while (!q.empty())
    {
        auto now = q.top().idx;
        q.pop();

        if (visited[now])
        {
            continue;
        }
        visited[now] = true;

        for (auto i = heads[now]; i; i = edges[i].next)
        {
            if (dis[start][edges[i].to] > dis[start][now] + edges[i].dis)
            {
                dis[start][edges[i].to] = dis[start][now] + edges[i].dis;

                if (!visited[edges[i].to])
                {
                    q.push(node{edges[i].to, dis[start][edges[i].to]});
                }
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::cin >> n >> q;

    for (auto i = 1; i <= n; i++)
    {
        std::cin >> c[i];
    }

    for (auto i = 1; i < n; i++)
    {
        std::cin >> u >> v >> w;

        add(u, v, w);
        add(v, u, w);
    }

    for (auto i = 1; i <= n; i++)
    {
        for (auto j = 1; j <= n; j++)
        {
            visited[j] = false;
            dis[i][j]  = 1e18;
        }

        dijkstra(i);
    }

    while (q--)
    {
        std::cin >> x >> y;

        long long ans = -1e18;
        for (auto i = 1; i <= n; i++)
        {
            ans = std::max(ans, c[x] + c[i] + c[y] - dis[x][i] - dis[i][y]);
        }

        std::cout << ans << "\n";
    }
}