记录编号	583572	评测结果	AAAAAAWAATTTTTTTTTTT
题目名称	坡伊踹	最终得分	40
用户昵称	心灵震荡	是否通过	未通过
代码语言	C++	运行时间	34.174 s
提交时间	2023-10-18 20:27:56	内存使用	31.40 MiB

// this is a test
#include <bits/stdc++.h>
using namespace std;
 
const int N=2e5+10;
 
int n,xun,idx,bsz,bcnt,idxx;
int head[N],nxt[2*N],ver[2*N],fa[N],daone[N],bl[N],br[N],bel[N],xiao[N];
 
bool dabiao1,dabiao2;
bool mk[N];
 
long long minn;
long long val[2*N],dis[2*N],a[N],sum[N];
 
struct node{
	int dian,zhi;
};
 
priority_queue <node> q;
 
bool operator < (const node &x,const node &y){
	return x.zhi>y.zhi;
}
 
inline int read(){
	int t=0,f=1;
	register char c=getchar();
	while(c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
	while(c>=48&&c<=57) t=(t<<3)+(t<<1)+(c^48),c=getchar();
	return t*f;
}
 
inline long long readl(){
	long long t=0,f=1;
	register char c=getchar();
	while(c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
	while(c>=48&&c<=57) t=(t<<3)+(t<<1)+(c^48),c=getchar();
	return t*f;
}
 
void add(int u,int v,long long w){
	nxt[++idx]=head[u];
	head[u]=idx;
	ver[idx]=v;
	val[idx]=w;
}
 
void dijkstra(int st){
	memset(mk,0,sizeof(mk));
	for(int i=1;i<=n;i++) dis[i]=(long long)(1e12);
	dis[st]=0;
	q.push((node){st,dis[st]});
	while(q.size()){
		node t=q.top();q.pop();
		if(mk[t.dian]) continue;
		mk[t.dian]=true;
//		cout<<"dian:"<<t.dian<<endl;
		for(int i=head[t.dian];i;i=nxt[i]){
			int dao=ver[i];
			if(dis[dao]>dis[t.dian]+val[i]){
//				cout<<"dao:"<<dao<<" ";
				dis[dao]=dis[t.dian]+val[i];
				fa[dao]=t.dian;
				q.push((node){dao,dis[dao]});
			}
		}
//		cout<<endl;
	}
}
 
long long minl(long long a,long long b){return (a>b)?(b):(a);}
 
long long maxl(long long a,long long b){return (a>b)?(a):(b);}
 
void init(){
	bsz=sqrt(n),bcnt=ceil((double)(n)/(double)(bsz));
	for(int i=1;i<=bcnt;i++){
		bl[i]=(i-1)*bsz+1,br[i]=i*bsz,sum[i]=(long long)(1e12);
		for(int j=bl[i];j<=br[i];j++){
			sum[i]=minl(sum[i],a[j]);
			bel[j]=i;
		}
	}
}
 
int erfen(int ll,int rr){
	bool xiada=false;
	if(ll>rr) {swap(ll,rr);xiada=true;}
//	cout<<ll<<" "<<rr<<endl;
	int l=1,r=idxx,mid;
	while(l<r){
		mid=(l+r+((xiada)?(1):(0)))/2;
		if(xiao[mid]<ll) l=mid+1;
		else if(xiao[mid]>rr) r=mid-1;
		else if(xiada) l=mid;
		else r=mid;
//		cout<<mid<<endl;
	}
	if(xiao[l]>=ll&&xiao[l]<=rr) return xiao[l];
	return 0;
}
 
int main(){
	freopen("poitry.in","r",stdin);
	freopen("poitry.out","w",stdout);
	dabiao1=true,dabiao2=true;
	n=read(),xun=read();
	for(int i=1;i<=n;i++) a[i]=read();
	init();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		if(x!=1) dabiao1=false;
		if(y!=x+1) dabiao2=false;
		long long z=readl();
		add(x,y,z),add(y,x,z);
	}
	if(dabiao1){
//		cout<<"YES"<<endl;
		for(int i=head[1];i;i=nxt[i]){
			daone[ver[i]]=val[i];
		}
//		for(int i=1;i<=n;i++) cout<<daone[i]<<" ";
//		cout<<endl;
		while(xun--){
			int x=read(),y=read();
			printf("%lld\n",minl(maxl(a[1],daone[x]),minl(a[x],maxl((long long)(daone[x]+daone[y]),a[y]))));
		}
		return 0;
	}
	if(dabiao2){
//		cout<<"Yess"<<endl;
		dijkstra(1);
		for(int i=1;i<=n;i++){
			if(a[i]<=dis[i]) xiao[++idxx]=i;
		}
		while(xun--){
			long long minn=(long long)(1e12);
			int x=read(),y=read();
			idxx=0;
			for(int i=min(x,y);i<=max(x,y);i++){
				if(a[i]<labs(dis[i]-dis[x])) xiao[++idxx]=i;
			}
			int zai=erfen(x,y);
//			cout<<zai<<endl;
			if(zai){
				if(zai<x) x=zai+1,y=x;
				else y=zai-1;
				if(bel[x]!=bel[y]){
					for(int i=x;i<=br[bel[x]];i++) minn=min(minn,a[i]);
					for(int i=bel[x]+1;i<=bel[y]-1;i++) minn=min(minn,sum[i]);
					for(int i=bl[bel[y]];i<=y;i++) minn=min(minn,a[i]);
				}else{
					for(int i=x;i<=y;i++) minn=min(minn,a[i]);
				}
//				cout<<minn<<" "<<dis[zai]<<endl;
				long long dang=labs(dis[zai]-dis[x]);
				if(minn<dang) printf("%lld\n",minn);
				else printf("%lld\n",dang);
				continue;
			}
			for(int i=x;i<=br[bel[x]];i++) minn=min(minn,a[i]);
			for(int i=bel[x]+1;i<=bel[y]-1;i++) minn=min(minn,sum[i]);
			for(int i=bl[bel[y]];i<=y;i++) minn=min(minn,a[i]);
			printf("%lld\n",minn); 
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<"i:"<<i<<endl;
//		for(int j=head[i];j;j=nxt[j]){
//			cout<<"dao:"<<ver[j]<<" val[j]"<<val[j]<<endl;
//		}
//		cout<<endl;
//	}
	while(xun--){
//		cout<<"YES"<<endl;
		int u=read(),v=read();
		if(u==v) {printf("%lld\n",a[u]);continue;}
		dijkstra(u);
//		cout<<endl;
//		for(int i=1;i<=n;i++) cout<<fa[i]<<" ";
//		cout<<endl;
//		for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
		minn=(long long)(1e12);
		while(1){
			minn=minl(minn,maxl(dis[v],a[v]));
			if(v==u) break;
//			if(a[v]<=dis[v]){minn=dis[v];break;} 
			v=fa[v];
		}
		printf("%lld\n",minn);
	}
	return 0;
}