HDU6393

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;

struct Edge{
    int u,v,w;
}E[N];

int ecnt;
int fir[N];
int nex[N<<1];
int to[N<<1];
int w[N<<1];

inline void addedge(int u,int v,int c){
    nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
    nex[++ecnt]=fir[v],fir[v]=ecnt,to[ecnt]=u,w[ecnt]=c;
}

int fa[N];
int siz[N];
int dep[N];
int son[N];
ll dis[N];
int U,V,W;

void dfs1(int x,int f){
    fa[x]=f;
    siz[x]=1;
    dep[x]=dep[f]+1;
    for(int i=fir[x];i;i=nex[i]){
        int v=to[i];
        if(v==f)continue;
        if(siz[v]){
            U=x,V=v,W=w[i];
            continue;
        }
        dis[v]=dis[x]+w[i];
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[son[x]]<siz[v])son[x]=v;
    }
}

int dfs_clock;
int top[N];
int dfn[N];
int ptn[N];

void dfs2(int x,int t){
    top[x]=t;
    dfn[x]=++dfs_clock;
    ptn[dfs_clock]=x;
    if(!son[x])return ;
    dfs2(son[x],t);
    for(int i=fir[x];i;i=nex[i]){
        int v=to[i];
        if(v==son[x]||v==fa[x])continue;
        if(x==U&&v==V)continue;
        dfs2(v,v);
    }
}

#define ls (rt<<1)
#define rs (rt<<1|1)
ll val[N<<2];
ll tag[N<<2];

void build(int rt,int l,int r){
    tag[rt]=0;
    if(l==r){
        int x=ptn[l];
        val[rt]=dis[x];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}

inline void pushdown(int rt){
    if(tag[rt]){
        val[ls]+=tag[rt];
        val[rs]+=tag[rt];
        tag[ls]+=tag[rt];
        tag[rs]+=tag[rt];
        tag[rt]=0;
    }
}

void modify(int rt,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        if(l==r)val[rt]+=v;
        else tag[rt]+=v;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid)modify(ls,l,mid,x,y,v);
    if(y>mid)modify(rs,mid+1,r,x,y,v);
}

ll query(int rt,int l,int r,int x){
    if(l==r)return val[rt];
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid)return query(ls,l,mid,x);
    else return query(rs,mid+1,r,x);
}

inline int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

int n,q;

inline ll dist(int u,int v){
    ll ret=0;
    ret+=query(1,1,n,dfn[u]);
    ret+=query(1,1,n,dfn[v]);
    ret-=2*query(1,1,n,dfn[lca(u,v)]);
    return ret;
}

inline void Modify(int x,int y){
    int u=E[x].u;
    int v=E[x].v;
    if(u==U&&v==V)W=y;
    else {
        int t=dep[u]<dep[v]?v:u;
        modify(1,1,n,dfn[t],dfn[t]+siz[t]-1,y-E[x].w);
        E[x].w=y;
    }
}

inline void Query(int x,int y){
    ll ans=dist(x,y);
    ans=min(ans,dist(x,U)+W+dist(V,y));
    ans=min(ans,dist(x,V)+W+dist(U,y));
    printf("%lld\n",ans);
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T;r(T);
    while(T--){
        r(n),r(q);
        ecnt=dfs_clock=0;
        memset(fir+1,0,n<<2);
        memset(siz+1,0,n<<2);
        memset(son+1,0,n<<2);
        for(int i=1;i<=n;++i){
            int u,v,c;
            r(u),r(v),r(c);
            E[i]=Edge{u,v,c};
            addedge(u,v,c);
        }
        dfs1(1,0);
        dfs2(1,0);
        build(1,1,n);
        while(q--){
            int opt,x,y;
            r(opt),r(x),r(y);
            if(opt)Query(x,y);
            else Modify(x,y);
        }
    }
    return 0;
}
/*
2
5 5
1 2 3
2 3 5
2 4 5
2 5 1
4 3 3
0 1 5
1 3 2
1 5 4
0 5 4
1 5 1
5 3
1 2 3
1 3 2
3 4 4
4 5 5
2 5 5
0 1 3
0 4 1
1 1 4

*/