取一棵生成森林，根据题目限制可得，与一个点相连的多余的边数是$O(\sqrt{m})$级别的。

对于树边，每个点维护3棵权值线段树，依次保存它的儿子里各个集合的边。

再开3*3个分块数组，记录多余边以及树边每种权值的出现次数，修改时暴力修改多余边，时间复杂度$O(q\sqrt{m})$。

 

#include
     
      #include
      
       using namespace std;const int N=100010,M=500010,P=2000000;char op[9];int n,m,Q,i,j,x,y,X,Y,f[N],c[N],ans;int g[N],ge[N],nxt[M<<1],v[M<<1],w[M<<1],ed,q[M][2],cnt,st[N],en[N];int fe[N],T[N][3],a[N][3];bool vis[N];int tot,l[P],r[P],val[P];struct E{int x,y,w;}e[M],b[M];inline bool cmp(const E&a,const E&b){  if(a.x==b.x)return a.y==b.y?a.w
       
        
         ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int F(int x){return f[x]==x?x:f[x]=F(f[x]);}inline void add(int x,int y,int z){  v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;  v[++ed]=x;w[ed]=z;nxt[ed]=g[y];g[y]=ed;}inline void adde(int x,int y,int z){  v[++ed]=y;w[ed]=z;nxt[ed]=ge[x];ge[x]=ed;  v[++ed]=x;w[ed]=z;nxt[ed]=ge[y];ge[y]=ed;}struct B{  bool v[M];int s[500];  inline void add(int x){v[x]=1,s[x>>10]++;}  inline void del(int x){v[x]=0,s[x>>10]--;}  inline int ask(){    for(int i=0;i<=m>>10;i++)if(s[i])for(int j=i<<10;;j++)if(v[j])return j;    return m+1;  }}V[3][3];void ins(int&x,int a,int b,int c,int p){  if(!x)x=++tot;val[x]+=p;  if(a==b)return;  int mid=(a+b)>>1;  if(c<=mid)ins(l[x],a,mid,c,p);else ins(r[x],mid+1,b,c,p);}inline int ask(int x){  if(!val[x])return m+1;  int a=1,b=m,mid;  while(a
         
          >1;    if(val[l[x]])x=l[x],b=mid;else x=r[x],a=mid+1;  }  return a;}void dfs(int x,int y,int z){  vis[x]=1,f[x]=y,fe[x]=z;  for(int i=g[x];i;i=nxt[i])if(!vis[v[i]]){    ins(T[x][0],1,m,w[i],1);    dfs(v[i],x,w[i]);  }  for(int i=0;i<3;i++)V[0][i].add(a[x][i]=ask(T[x][i]));}int main(){  read(n),read(m);  for(i=1;i<=n;i++)f[i]=i;  for(i=1;i<=m;i++){    read(e[i].x),read(e[i].y),read(e[i].w);    if(e[i].x>e[i].y)swap(e[i].x,e[i].y);  }  sort(e+1,e+m+1,cmp);  for(i=1;i<=m;i++)if(e[i].x!=e[i-1].x||e[i].y!=e[i-1].y)b[++j]=e[i];  for(m=j,sort(b+1,b+m+1,cmp2),i=1;i<=m;i++){    x=b[i].x,y=b[i].y;    if(F(x)!=F(y))f[f[x]]=f[y],add(x,y,i);else adde(x,y,i);  }  for(i=1;i<=n;en[i++]=cnt){    if(!vis[i])dfs(i,0,0);    for(st[i]=cnt+1,j=ge[i];j;j=nxt[j]){      if(v[j]