RT，除了1~4其余全T

#include<bits/stdc++.h>
using namespace std;
const long long INF=123456789123456789;
int n,q,dfn[100005],rdfn[100005],wc[100005],siz[100005],top[100005],cnt,dep[100005],fa[100005];
long long dis[100005];
struct edge{int to,w;};
vector<edge>e[100005];
void dfs1(int now,int fa,long long len){
	dis[now]=len;
	dep[now]=dep[fa]+1;
	::fa[now]=fa;
	for(auto it:e[now]){
		if(it.to!=fa){
			dfs1(it.to,now,len+it.w);
			siz[now]+=siz[it.to];
			if(siz[it.to]>siz[wc[now]])    wc[now]=it.to;
		}
	}
}
void dfs2(int now,int fa,int Top){
	dfn[now]=++cnt;
	rdfn[cnt]=now;
	top[now]=Top;
	if(wc[now]) dfs2(wc[now],now,Top);
	for(auto it:e[now]){
		if(it.to!=fa&&it.to!=wc[now])   dfs2(it.to,now,it.to);
	}
}
struct line{
	long long k,b;
	long long calc(long long x){return k*dis[rdfn[x]]+b;}
};
struct LCT{
	line li[200020];
	int lazy[400020],num_line=0;
	long long ans[400020];
	inline int ls(int x){return x<<1;}
	inline int rs(int x){return x<<1|1;}
	inline void pushup(int x,int l,int r){
		ans[x]=min(ans[x],min(ans[ls(x)],ans[rs(x)]));
		ans[x]=min(ans[x],min(li[lazy[x]].calc(l),li[lazy[x]].calc(r)));
	}
//	void pushdown(int x){
//		ans[ls(x)]=min(ans[ls(x)],ans[x]);
//		ans[rs(x)]=min(ans[rs(x)],ans[x]);
//	}
	void build(int p,int l,int r){
		ans[p]=INF;
		if(l==r)	return;
		int mid=(l+r)>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
	}
	int cmp(line a,line b,long long x){
		long long vala=a.calc(x),valb=b.calc(x);
		return vala<valb;
	}
	void change(int p,int l,int r,int num){
		int mid=(l+r)>>1;
		if(cmp(li[num],li[lazy[p]],mid))	swap(num,lazy[p]);
		if(l==r){
			ans[p]=li[lazy[p]].calc(mid);
			return;
		}
		if(cmp(li[num],li[lazy[p]],l))	change(ls(p),l,mid,num);
		if(cmp(li[num],li[lazy[p]],r))	change(rs(p),mid+1,r,num);
		pushup(p,l,r);
	}
	void update(int p,int l,int r,int re_l,int re_r,int num){
		if(l>=re_l&&r<=re_r)    change(p,l,r,num);
		else if(!(r<re_l||l>re_r)){
			int mid=(l+r)>>1;
			update(ls(p),l,mid,re_l,re_r,num);
			update(rs(p),mid+1,r,re_l,re_r,num);
			pushup(p,l,r);
		}
	}
	long long query(int p,int l,int r,int re_l,int re_r){
		if(l>=re_l&&r<=re_r)	return ans[p];
		else if(!(r<re_l||l>re_r)){
			int mid=(l+r)>>1;
			long long ret=min(li[lazy[p]].calc(max(re_l,l)),li[lazy[p]].calc(max(re_r,r)));
			return min(ret,min(query(ls(p),l,mid,re_l,re_r),query(rs(p),mid+1,r,re_l,re_r)));
		}
		return INF;
	}
}T;
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		x=fa[top[x]];
	}
	return (dep[x]<dep[y]?x:y); 
}
void chan(int x,int y,int l){
	while(top[x]!=top[y])	T.update(1,1,n,dfn[top[x]],dfn[x],l),x=fa[top[x]];
	T.update(1,1,n,dfn[y],dfn[x],l);
}
void upd(int x,int y,long long a,long long b){
	int lca=LCA(x,y);
	T.li[++T.num_line]={-a,dis[x]*a+b};
	chan(x,lca,T.num_line);
	T.li[++T.num_line]={a,dis[x]*a-dis[lca]*2*a+b};
	chan(y,lca,T.num_line);
}
long long qry(int x,int y){
	long long ret=INF;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		ret=min(ret,T.query(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	return min(ret,T.query(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1,u,v,w;i<n;i++){
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	dfs1(1,0,0);
	dfs2(1,0,1);
	T.li[0]={0,INF};
	T.build(1,1,n);
	for(int i=1,opt,s,t,a,b;i<=q;i++){
		cin>>opt>>s>>t;
		if(opt==1){
			cin>>a>>b;
			upd(s,t,a,b);
		}else	cout<<qry(s,t)<<"\n";
	}
}