rt，分层图spfa跑了72分，超越我们机房一众dijkstra和纯树剖:)

#include "bits/stdc++.h"

#define ll long long
#define endl "\n"
#define maxn 200005

using namespace std;

ll read(){
    ll f = 1,k = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -f;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        k = (k<<1)+(k<<3)+c-48;
        c = getchar();
    }
    return f*k;
}

struct Query{
    int u,v,id;
    ll ans;
}query[maxn];

struct Edge{
    int v;
    ll w;
};

int n,q;
ll val[maxn],dis[maxn<<1],vis[maxn<<1];
vector<Edge> E[maxn<<1];

void insert(int u,int v,ll w){
    E[u].push_back(Edge{v,w});
    return;
}

void dijkstra(int x){
    for(int i = 1;i <= 2*n;i++){
        dis[i] = LONG_LONG_MAX;
        vis[i] = 0;
    }
    queue<pair<ll,int>> pq;
    dis[x] = 0;
    pq.push({0,x});
    while(!pq.empty()){
        int u = pq.front().second;pq.pop();
        vis[u] = 0;
        for(auto [v,w]:E[u]){
            if(dis[v] > dis[u]+w){
                dis[v] = dis[u]+w;
                if(!vis[v]){
                    vis[v] = 1;
                    pq.push({dis[v],v});
                } 
            }
        }
    }
}

bool cmp(Query x,Query y){
    if(x.u == y.u){
        return x.v < y.v;
    }else return x.u < y.u;
}
bool cmp2(Query x,Query y){
    return x.id < y.id;
}

int main(){
    n = read();q = read();
    for(int i = 1;i <= n;i++)   val[i] = read();
    for(int i = 1;i < n;i++){
        int u = read(),v = read();ll w = read();
        insert(u,v,w);
        insert(v,u,w);
        insert(u+n,v+n,w);
        insert(v+n,u+n,w);
        insert(u,v+n,w-val[v]);
        insert(v,u+n,w-val[u]);
    }
    for(int i = 1;i <= n;i++) insert(i,i+n,-val[i]);
    dijkstra(1);
    for(int i = 1;i <= q;i++){
        int u = read(),v = read();
        if(u > v) swap(u,v);
        query[i] = {u,v,i};
    }
    sort(query+1,query+1+q,cmp);
    for(int i = 1;i <= q;){
        int u = query[i].u;
        dijkstra(u);
        while(query[i].u == u){
            int v = query[i].v;
            query[i].ans = val[u]+val[v]-dis[v+n];
            i++;
        }
    }
    sort(query+1,query+1+q,cmp2);
    for(int i = 1;i <= q;i++){
        cout << query[i].ans << endl;
    }
    return 0;
}