LCT维护一下和温度最值维护一下最小大成树就可以了
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ob,*ib;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
const int N=400005;
int a[N],tp[N],val[N];
struct edge{
int u,v;
}e[N];
namespace Lct{
int q[N],fa[N],son[N][2],rev[N],pos[N],sum[N];
#define lc(u) son[u][0]
#define rc(u) son[u][1]
inline bool isrt(int u){
if(!fa[u])return 1;
return lc(fa[u])!=u&&rc(fa[u])!=u;
}
inline bool isrc(int u){
return rc(fa[u])==u;
}
inline void pushup(int u){
pos[u]=u,sum[u]=val[u]+sum[lc(u)]+sum[rc(u)];
if(lc(u)&&tp[pos[u]]>tp[pos[lc(u)]])pos[u]=pos[lc(u)];
if(rc(u)&&tp[pos[u]]>tp[pos[rc(u)]])pos[u]=pos[rc(u)];
}
inline void pushdown(int u){
if(!rev[u])return;
if(lc(u))rev[lc(u)]^=1;
if(rc(u))rev[rc(u)]^=1;
swap(lc(u),rc(u)),rev[u]=0;
}
inline void rotate(int v){
int u=fa[v],z=fa[u];
int t=rc(u)==v;
if(!isrt(u))son[z][rc(z)==u]=v;
fa[v]=z;
son[u][t]=son[v][t^1];
fa[son[v][t^1]]=u;
fa[u]=v,son[v][t^1]=u;
pushup(u),pushup(v);
}
inline void splay(int u){
q[q[0]=1]=u;
for(int v=u;!isrt(v);v=fa[v])q[++q[0]]=fa[v];
for(int i=q[0];i;i--)pushdown(q[i]);
while(!isrt(u)){
if(!isrt(fa[u]))
isrc(u)==isrc(fa[u])?rotate(fa[u]):rotate(u);
rotate(u);
}
}
inline void access(int u){
for(int v=0;u;v=u,u=fa[u]){
splay(u),rc(u)=v;if(v)fa[v]=u;pushup(u);
}
}
inline void makert(int u){
access(u),splay(u),rev[u]^=1;
}
inline void link(int u,int v){
makert(u),splay(v),fa[u]=v,pushup(v);
}
inline void cut(int u,int v){
makert(u),access(v),splay(v),lc(v)=fa[u]=0;
}
inline int findrt(int u){
access(u),splay(u);while(pushdown(u),lc(u))u=lc(u);
splay(u);return u;
}
}
using namespace Lct;
char op[10];
int n,m;
int f[N];
inline int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)tp[i]=2e9,f[i]=i;
while(m--){
scanf("%s",op);
if(op[0]=='f'){
int id=read()+n+1,u=read()+1,v=read()+1;
e[id].u=u,e[id].v=v,tp[id]=read(),val[id]=read();
if(find(u)!=find(v)){
link(id,u);f[u]=v;
link(id,v);
}
else{
makert(u),access(v),splay(v);
if(tp[pos[v]]<tp[id]){
int p=pos[v];
cut(p,e[p].u),cut(p,e[p].v);
link(id,u),link(id,v);
}
}
}
else if(op[0]=='m'){
int u=read()+1,v=read()+1;
if(find(u)!=find(v))puts("-1");
else{
makert(u),access(v),splay(v);
cout<<sum[v]<<'
';
}
}
else{
int u=read()+n+1,k=read();
makert(u),splay(u),val[u]=k,pushup(u);
}
}
}