#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;
using namespace chrono;
typedef signed char i8;typedef short i16;typedef int i32;typedef long long i64;typedef unsigned char u8;typedef unsigned short u16;typedef unsigned u32;typedef unsigned long long u64;typedef float f32;typedef double f64;typedef long double f96;
template<typename A,typename B>void to_max(A& a,B b){if(a<b)a=b;}
template<typename A,typename B>void to_min(A& a,B b){if(b<a)a=b;}

constexpr int N(1e5+5);
constexpr i64 INF(1e18);
char ___tp[15];
int n,m,rk[N];
i64 f[N][2],a[N][2];
vector<int> g[N];
struct matrix{
	i64 a[2][2];
	matrix(){memset(a,0x3f,sizeof(a));}
	matrix(const matrix& b){
		memcpy(a,b.a,sizeof(a));
	}
	matrix(matrix&& b){
		memcpy(a,b.a,sizeof(a));
	}
	matrix& operator=(const matrix& b){
		memcpy(a,b.a,sizeof(a));
		return *this;
	}
	matrix& operator=(matrix&& b){
		memcpy(a,b.a,sizeof(a));
		return *this;
	}
	i64* operator[](int k){
		return a[k];
	}
	matrix operator*(matrix b){
		i8 i,j,k;
		matrix c;
		for(k=0;k<2;++k){
			for(i=0;i<2;++i){
				for(j=0;j<2;++j){
					to_min(c[i][j],a[i][k]+b[k][j]);
				}
			}
		}
		return c;
	}
}val[N];
namespace segment_tree{
	struct node{
		int l,r;
		matrix a;
	}t[N<<2];
	#define ls u<<1
	#define rs u<<1|1
	void push_up(int u){
		t[u].a=t[ls].a*t[rs].a;
	}
	void build(int u=1,int l=1,int r=n){
		t[u].l=l;t[u].r=r;
		if(l==r){
			t[u].a=val[rk[l]];
			return;
		}
		const int mid((l+r)>>1);
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(u);
	}
	void update(int x,int u=1){
		if(t[u].l==t[u].r){
			t[u].a=val[rk[t[u].l]];
			return;
		}
		const int mid((t[u].l+t[u].r)>>1);
		x<=mid?update(x,ls):update(x,rs);
		push_up(u);
	}
	matrix query(int x,int y,int u=1){
		if(x<=t[u].l&&t[u].r<=y){
			return t[u].a;
		}
		const int mid((t[u].l+t[u].r)>>1);
		if(x<=mid&&mid<y){
			return query(x,y,ls)*query(x,y,rs);
		}else if(x<=mid){
			return query(x,y,ls);
		}else{
			return query(x,y,rs);
		}
	}
	#undef ls
	#undef rs
}
namespace split_tree{
	int dfn[N],dfe[N],dfc,fa[N],son[N],sz[N],top[N];
	void dfs1(int u,int father){
		sz[u]=1;fa[u]=father;
		for(int& v:g[u]){
			if(v!=father){
				dfs1(v,u);
				sz[u]+=sz[v];
				if(sz[v]>sz[son[u]]){
					son[u]=v;
				}
			}
		}
	}
	void dfs2(int u,int head){
		rk[dfn[u]=dfe[head]=++dfc]=u;
		top[u]=head;
		f[u][0]=val[u][0][1]=a[u][0];
		f[u][1]=val[u][1][0]=a[u][1];
		if(son[u]){
			dfs2(son[u],head);
			f[u][0]+=f[son[u]][1];
			f[u][1]+=min(f[son[u]][0],f[son[u]][1]);
			for(int& v:g[u]){
				if(v!=son[u]&&v!=fa[u]){
					dfs2(v,v);
					f[u][0]+=f[v][1];
					f[u][1]+=min(f[v][0],f[v][1]);
					val[u][0][1]+=f[v][1];
					val[u][1][0]+=min(f[v][0],f[v][1]);
				}
			}
		}
		val[u][1][1]=val[u][1][0];
	}
	void update(int u,bool x,i64 new_val){
		matrix bef,aft;
		if(x){
			val[u][1][0]+=new_val-a[u][x];
			val[u][1][1]=val[u][1][0];
		}else{
			val[u][0][1]+=new_val-a[u][x];
		}
		a[u][x]=new_val;
		while(u){
			bef=segment_tree::query(dfn[top[u]],dfe[top[u]]);
			segment_tree::update(dfn[u]);
			aft=segment_tree::query(dfn[top[u]],dfe[top[u]]);
			u=fa[top[u]];
			if(!u){
				break;
			}
			val[u][0][1]+=aft[1][0]-bef[1][0];
			val[u][1][0]+=min(aft[0][0],aft[1][0])-min(bef[0][0],bef[1][0]);
			val[u][1][1]=val[u][1][0];
		}
	}
	i64 get_ans(){
		matrix a(segment_tree::query(dfn[1],dfe[1]));
		i64 res(min(a[0][1],a[1][1]));
		return res<1e10?res:-1;
	}
}
int main(){
	i8 x,y;
	int i,u,v;
	i64 old_u,old_v;
	scanf("%d%d%s",&n,&m,___tp);
	for(i=1;i<=n;++i){
		scanf("%lld",a[i]+1);
	}
	for(i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	split_tree::dfs1(1,0);
	split_tree::dfs2(1,1);
	segment_tree::build();debug("ans=%lld\n",split_tree::get_ans());
	for(i=1;i<=m;++i){
		scanf("%d%hhd%d%hhd",&u,&x,&v,&y);
		x^=1;y^=1;
		old_u=a[u][x];old_v=a[v][y];
		split_tree::update(u,x,INF);
		split_tree::update(v,y,INF);
		printf("%lld\n",split_tree::get_ans());
		split_tree::update(u,x,old_u);
		split_tree::update(v,y,old_v);
	}
	return 0;
}