RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=3e5+5,MAXM=3e5+5;
ll n,m,x,y,z;
ll op,s,t,LCA;
struct edge{
	ll u,v,w,nxt;
}e[MAXM];
ll head[MAXN],edge_num;
void add_edge(ll From,ll To,ll Len){
	edge_num++;
	e[edge_num].u=From;
	e[edge_num].v=To;
	e[edge_num].w=Len;
	e[edge_num].nxt=head[From];
	head[From]=edge_num;
	return;
}
ll fa[MAXN],deep[MAXN],dis[MAXN],sz[MAXN],hson[MAXN];
void pre(ll now,ll father){
	fa[now]=father;
	deep[now]=deep[fa[now]]+1;
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].v==father)continue;
		dis[e[i].v]=dis[now]+e[i].w;
		pre(e[i].v,now);
		sz[now]+=sz[e[i].v];
		if(sz[e[i].v]>sz[hson[now]])hson[now]=e[i].v;
	}
	return;
}
ll dfn[MAXN],rk[MAXN],cnt,top[MAXN];
void cut(ll now,ll rt){
	dfn[now]=++cnt;
	rk[cnt]=now;
	top[now]=rt;
	if(hson[now])cut(hson[now],rt);
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].v==fa[now]||e[i].v==hson[now])continue;
		cut(e[i].v,e[i].v);
	}
	return;
}
ll lca(ll X,ll Y){
	while(top[X]!=top[Y]){
		if(deep[top[X]]<deep[top[Y]])swap(X,Y);
		X=fa[top[X]];
	}
	return deep[X]<deep[Y]?X:Y;
} 
struct line{
	ll k,b;
	ll calc(ll num){
		return dis[num]*k+b;
	}
}Line[MAXN];
ll tot;
struct sgm_t{
	ll tree[MAXN<<2],min_p[MAXN<<2];
	void init(){
		memset(tree,0,sizeof(tree));
		for(int i=0;i<=(MAXN<<2)-5;i++)min_p[i]=123456789123456789;
		return;
	}
	void update(ll id,ll L,ll R,ll UL,ll UR,ll k){
		if(L>R||L>UR||R<UL)return;
		ll mid=(L+R)>>1; 
		if(UL<=L&&R<=UR){
			if(Line[tree[id]].calc(mid)>Line[k].calc(mid))swap(tree[id],k);
			min_p[id]=min(min_p[id],min(Line[tree[id]].calc(L),Line[tree[id]].calc(R)));
			if(Line[tree[id]].calc(L)>Line[k].calc(L))update(id<<1,L,mid,UL,UR,k);
			if(Line[tree[id]].calc(R)>Line[k].calc(R))update(id<<1|1,mid+1,R,UL,UR,k);
			min_p[id]=min(min_p[id],min(min_p[id<<1],min_p[id<<1|1]));
			return;
		}
		update(id<<1,L,mid,UL,UR,k);
		update(id<<1|1,mid+1,R,UL,UR,k);
		min_p[id]=min(min_p[id],min(min_p[id<<1],min_p[id<<1|1]));
		return;
	}
	ll query(ll id,ll L,ll R,ll QL,ll QR){
		if(L>R||L>QR||R<QL)return 123456789123456789;
		if(QL<=L&&R<=QR){
//			if(min_p[id]==0)cout<<"error"<<endl;
			return min_p[id];
		}
		ll mid=(L+R)>>1,ans=123456789123456789;
		if(Line[tree[id]].b!=123456789123456789)ans=min(ans,min(Line[tree[id]].calc(max(L,QL)),Line[tree[id]].calc(min(R,QR))));
		ans=min(ans,min(query(id<<1,L,mid,QL,QR),query(id<<1|1,mid+1,R,QL,QR)));
		return ans;
	} 
}S;
void update_tree(ll X,ll Y){
	while(top[X]!=top[Y]){
		S.update(1,1,n,dfn[top[X]],dfn[X],tot);
		X=fa[top[X]];
	}
	S.update(1,1,n,dfn[Y],dfn[X],tot);
	return;
}
ll query_tree(ll X,ll Y){
	ll ans=123456789123456789;
	while(top[X]!=top[Y]){
		if(deep[top[X]]<deep[top[Y]])swap(X,Y);
		ans=min(ans,S.query(1,1,n,dfn[top[X]],dfn[X]));
		X=fa[top[X]];
	}
	if(dfn[X]>dfn[y])swap(X,Y);
	return min(ans,S.query(1,1,n,dfn[X],dfn[Y]));
}
int main(){
//	freopen("sss.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		cin>>x>>y>>z;
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	pre(1,0);
	cut(1,1); 
	Line[0]=(line){0,123456789123456789};
	S.init();
//	for(int i=1;i<=n;i++)cout<<fa[i]<<" "<<deep[i]<<" "<<top[i]<<" "<<dis[i]<<endl;
	for(int i=1;i<=m;i++){
		cin>>op>>s>>t;
		if(op==1){
			cin>>x>>y;
			LCA=lca(s,t);
			Line[++tot]=(line){-x,x*dis[s]+y};
			update_tree(s,LCA);
			Line[++tot]=(line){x,x*(dis[s]-2*dis[LCA])+y};
			update_tree(t,LCA);
		}
		else cout<<query_tree(s,t)<<'\n';
	}
	return 0;
}

样例过了