不难发现肯定是在温度的最大生成树上走是最优的

于是用\(LCT\)维护最大生成树，每一次加边时如果已经连通，就判断一下路径上的最小温度是否小于当前温度，是的话就断掉那条边，加入新边

//minamoto#include
    
     #define R register#define fi first#define se second#define pi pair
     
      #define fp(i,a,b) for(R int i=a,I=b+1;i
      
       I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}inline char getop(){char ch;while((ch=getc())!='f'&&ch!='m'&&ch!='c');return ch;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=4e5+5;int ch[N][2],fa[N],v[N],sum[N],f[N],w[N],px[N],py[N];bool rev[N];pi mn[N];int n,m,id,x,y,t,l,zz;char op;int find(int x){return f[x]==x?x:f[x]=find(f[x]);}inline bool is(R int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}void upd(R int x){    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+w[x];    mn[x]=min(pi(v[x],x),min(mn[ch[x][0]],mn[ch[x][1]]));}inline void ppd(R int x){swap(ch[x][0],ch[x][1]),rev[x]^=1;}inline void pd(R int x){if(rev[x])ppd(ch[x][0]),ppd(ch[x][1]),rev[x]=0;}void update(R int x){if(!is(x))update(fa[x]);pd(x);}void rotate(int x){    int y=fa[x],z=fa[y],d=ch[y][1]==x;    if(!is(y))ch[z][ch[z][1]==y]=x;    fa[x]=z,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y,fa[y]=x,upd(y);}void splay(int x){    update(x);    for(R int y=fa[x],z=fa[y];!is(x);y=fa[x],z=fa[y]){        if(!is(y))(ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y);        rotate(x);    }upd(x);}inline void access(int x){    int t=0;    while(x)splay(x),ch[x][1]=t,upd(x),t=x,x=fa[x];}inline void makert(int x){    access(x),splay(x),ppd(x);}inline void split(int x,int y){    makert(x),access(y),splay(y);}inline void link(int x,int y){    makert(x),fa[x]=y;}inline void cut(int x,int y){    split(x,y),fa[x]=ch[y][0]=0,upd(y);}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read();    mn[0]=pi(1<<30,0);    fp(i,1,n)f[i]=i,v[i]=1<<30,mn[i]=pi(v[i],i);    while(m--){        op=getop();        switch(op){            case 'f':{                id=read()+1,x=read()+1,y=read()+1,t=read(),l=read();                v[id+n]=t,sum[id+n]=w[id+n]=l,mn[id+n]=pi(v[id+n],id+n);                px[id]=x,py[id]=y;                if(find(x)!=find(y))link(id+n,x),link(id+n,y),f[f[x]]=f[y];                else{                    split(x,y);                    if(mn[y].fi