#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn=1e5+;

int n,q,head[maxn],tot,u,v,fa[maxn],sc,me[maxn],size[maxn],l[maxn],r[maxn],fin[maxn],son[maxn];

int dep[maxn],top[maxn],hold[maxn];

ll sum[maxn<<];

ll w,val[maxn];

struct edge{

    int u,v,id;

    ll w;

}a[maxn];

vector<edge >ve[maxn];

void init(){

    tot=;

    for(int i=;i<=n;i++){

        me[i]=i;

    }

    for(int i=;i<=n;i++){

        ve[i].clear();

    }

}

int find(int x){

    return x==me[x]?x:me[x]=find(me[x]);

}

void build(int o,int ql,int qr){

    if(ql==qr){

        sum[o]=val[fin[ql]];

//        printf("ql:%d  qr:%d  sum[o]:%d  fin[ql]:%d\n",ql,qr,sum[o],fin[ql]);

        return;

    }

    int mid=(ql+qr)>>;

    build(o<<,ql,mid);

    build(o<<|,mid+,qr);

    sum[o]=sum[o<<]+sum[o<<|];

}

void update(int o,int ql,int qr,int p,int v){

    if(ql==qr){

        sum[o]=v;

        return;

    }

    int mid=(ql+qr)>>;

    if(p<=mid)update(o<<,ql,mid,p,v);

    else update(o<<|,mid+,qr,p,v);

    sum[o]=sum[o<<]+sum[o<<|];

}

ll query(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr)return sum[o];

    int mid=(l+r)>>;

    ll res=;

    if(ql<=mid)res+=query(o<<,l,mid,ql,qr);

    if(qr>mid)res+=query(o<<|,mid+,r,ql,qr);

    return res;

}

inline ll get(int x)

{

    ll ret = ;

    while(top[x]!=)

    {

//        printf("top[x]:%d\n",top[x]);

        ret+=query(,,n,l[top[x]],l[x]);

        x=fa[top[x]];

    }

    ret+=query(,,n,,l[x]);

    return ret;

}

int lca(int x,int y){

    while(top[x]!=top[y])

        {

            if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];

            else y=fa[top[y]];

        }

    return dep[x]<dep[y]?x:y;

}

inline void dfs_1(int x,int pre)

{

//    printf("x:%d  pre:%d\n",x,pre);

    fa[x] = pre;

    son[x] = -;

    size[x] = ;

    dep[x] = dep[pre]+;

    int si=ve[x].size();

    for(int i = ; i < si; i++){

        int v=ve[x][i].v;

        if( v!= pre)

        {

            val[v]=ve[x][i].w;

            hold[ve[x][i].id]=v;

            dfs_1(v,x);

            size[x] += size[v];

            if(son[x]==- || size[v]>size[son[x]]) son[x] = v;

        }

    }

}

inline void dfs_2(int x,int root)

{

    top[x] = root;

    l[x]  = ++tot;

    fin[l[x]] = x;

    if(son[x] != -)

    dfs_2(son[x],root);

    int si=ve[x].size();

    for(int i = ; i < si; i++){

        int v=ve[x][i].v;

        if(v != fa[x] && v != son[x])

            dfs_2(v,v);

        }

    r[x]=tot;

}

int main(){

    int T;

    cin>>T;

    while(T--){

        scanf("%d%d",&n,&q);

        init();

        for(int i=;i<=n;i++){

            scanf("%d%d%lld",&a[i].u,&a[i].v,&a[i].w);

            a[i].id=i;

            int fu=find(a[i].u),fv=find(a[i].v);

//            printf("u:%d  v:%d  fu:%d  fv:%d\n",u,v,fu,fv);

            if(fu!=fv){

                me[fu]=fv;

                ve[a[i].u].push_back({a[i].u,a[i].v,i,a[i].w});

                ve[a[i].v].push_back({a[i].v,a[i].u,i,a[i].w});

            }else{

                sc=i;

            }

        }

        dfs_1(,);

//        printf("debug\n");

        dfs_2(,);

        build(,,n);

        int op,x,y;

        while(q--){

            scanf("%d%d%d",&op,&x,&y);

            if(op==){

                if(x==sc){

                    a[sc].w=y;

                }else{

                    update(,,n,l[hold[x]],y);

                }

            }else{

                int lc=lca(x,y);

                ll ans=get(x)+get(y)-*get(lc);

                ll res1=get(x)+get(a[sc].u)-*(get(lca(x,a[sc].u)))+get(y)+get(a[sc].v)-*(get(lca(y,a[sc].v)));

                ll res2=get(x)+get(a[sc].v)-*(get(lca(x,a[sc].v)))+get(y)+get(a[sc].u)-*(get(lca(y,a[sc].u)));

                printf("%lld\n",min(ans,a[sc].w+min(res1,res2)));

            }

        }

    }

}