题意：

一个n个点，n条边的图，2中操作，1是将某条边的权值更改，2是询问两点的最短距离。

题解： 

由于n个点，n条边，所以是树加一个环，将环上的边随意取出一条，就是1颗树，以取出的边的一个端点为根，建立有根树。虚线就是取出的边。红色为环上的边。

对于更改边的权值的操作，用dfs序+区间修改点查询的树状树组维护。

对于询问最短路的操作，用LCA分类解决。假设询问的两点是x、y，LCA是 z。

  • 若z不是环上的点，那么最短路就是：x到根的距离+y到根的距离-z到根的距离*2；
  • 若z是环上的点，最短路可能是经过图中红线的路径，也可能是经过图中虚线的路径，取最短的即可。

代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 100010
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define eps 1e-8
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mem(x) memset(x,0,sizeof x )
using namespace std;
int st[N],en[N],fa[N],L[N],a[N],b[N],c[N],e[N],w[N],r[N],anc[N][19],la[N];
int t,n,m,o;
LL d[N];int tt=0;
struct node { int f,s,l;}G[N<<1];
bool fg[N];

inline void add(int u,int v,int id)
{
    G[++t].f=v;
    G[t].s=id;
    G[t].l=la[u];
    la[u]=t;
}

void preprocess()
{
    for (int i=1;i<=n;i++)
    {
        anc[i][0]=fa[i];
        for (int j=1;(1<<j)<=n;j++) anc[i][j]=-1;
    }
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i<=n;i++)
            if (anc[i][j-1]!=-1) anc[i][j]=anc[anc[i][j-1]][j-1];
}

int query(int p,int q)
{
    int log;
    if (L[p]<L[q]) swap(p,q);
    for (log=1;(1<<log)<=L[p];log++);log--;

    for (int i=log;i>=0;i--)
        if (L[p]-(1<<i)>=L[q])p=anc[p][i];

    if (p==q)return p;

    for (int i=log;i>=0;i--)if (anc[p][i]!=-1 && anc[p][i]!=anc[q][i])
    {
        p=anc[p][i];
        q=anc[q][i];
    }
    return fa[p];
}
int getfa(int x)
{
    return fa[x]==x? x: fa[x]=getfa(fa[x]);
}

void updata(int x,int w)
{
    for (;x<N;x+=x&-x) d[x]+=w;
}

LL sum(int x)
{
    LL t=0;
    for (;x;x-=x&-x) t+=d[x];
    return t;
}

void ddfs(int x)
{
    st[x]=++t;
    for (int i=la[x];i;i=G[i].l)
    {
        int f=G[i].f,s=G[i].s;
        if (fg[f]) continue;
        fg[f]=1;
        fa[f]=x;
        L[f]=L[x]+1;
        c[s]=f;
        r[f]=w[s];
        ddfs(f);
    }
    en[x]=t;
}

void dfs(int x)
{
    for (int i=la[x];i;i=G[i].l)
    {
        if (L[G[i].f]>L[x] && !e[G[i].f])
        {
            a[G[i].f]=t;
            dfs(G[i].f);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        tt++;
        scanf("%d%d",&n,&m);
        mem(st);
        mem(en);
        mem(L);
        mem(c);
        mem(e);
        mem(r);
        mem(la);
        mem(anc);
        mem(G);
        mem(d);
        mem(fg);
        for (int i=1;i<=n;i++) fa[i]=i;
        t=0;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i],&b[i],&w[i]);
            int p=getfa(a[i]),q=getfa(b[i]);
            if (p!=q)
            {
                fa[p]=q;
                add(a[i],b[i],i);
                add(b[i],a[i],i);
            }else o=i;
        }


        fg[a[o]]=1; t=0; ddfs(a[o]);


        LL tot=w[o];
        for (int i=1;i<=n;i++) if(i!=a[o])
        {
            updata(st[i],r[i]);
            updata(en[i]+1,-r[i]);
        }

        fa[a[o]]=0; for (int i=b[o];i;i=fa[i]) e[i]=1,tot+=r[i];

        for (int i=1;i<=n;i++) if (e[i])
        {
            t=i; a[i]=i;
            dfs(i);
        }

        preprocess();
        while(m--)
        {
            int op,p,q;
            scanf("%d%d%d",&op,&p,&q);
            if (op==0)
            {
                if (p==o)
                {
                    tot=tot-w[o]+q;
                    w[o]=q;
                    continue;
                }
                t=c[p];
                if(e[t]) tot=tot-r[t]+q;
                updata(st[t],q-r[t]);
                updata(en[t]+1,r[t]-q);
                r[t]=q;
            }else
            {
                int lca=query(p,q);
                if (e[lca])
                {
                    int t1=a[p],t2=a[q];
                    LL ans=sum(st[p])-sum(st[t1]);
                    ans=ans+sum(st[q])-sum(st[t2]);
                    if (L[t1]>L[t2]) swap(t1,t2);
                    LL t3=sum(st[t2])-sum(st[t1]);
                    t3=min(t3,tot-t3);
                    printf("%I64d\n",ans+t3);
                }
                else printf("%I64d\n",sum(st[p])+sum(st[q])-sum(st[lca])*2);
            }
        }
    }
}