模拟赛：0(100->5)+0(100)+0+0(75)

T1：

好像要枚举logn个，但我貌似只枚举到s[15]?
(5分是忘了去输出调试了)

T2：

一眼顶针，鉴定为暴力就行
（不开O2见祖宗）

T3（假）：

优先队列貌似没法实时更改标记
直接爆改换set

T3（真）：

cqr：我们要充分发扬人类智慧

实际上倍增跳点就好了

T5：

一题更比五题强

观察到只会取一条非树边，考虑枚举这条边

算法一（赛时）：

对于每条非树边，考虑怎样会对答案产生贡献？
显然是树上距离>=[n/3]的点(废话)
树边的作用为“短路最长链”
那么对于一颗子树中轻链，往下走时的可能树边会直接变成常数级别
同理重链也是，可能树边答案总数貌似是log^2(n)?
考虑对所有重链暴力建边跑最短路，继承轻链信息
复杂度没认真分析，貌似是O（nlog^3(n)）

算法二（赛后）：

短路的思路是对了，不过暴力建边跑最短路可以用超级大分讨解决
代码不长非常难写

而且写挂了还只有36分！

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5,maxm=2e6,inf=1e9;
int n,m;
vector<int> g[maxn+5],num[maxn+5],qing[maxn+5];
int top[maxn+5],cnt,dtot,btot,dep[maxn+5],ans,wso[maxn+5],fa[maxn+5],siz[maxn+5],mxdep[maxn+5],mxdepsec[maxn+5],bfn[maxn+5],bpre[maxn+5],updep[maxn+5],updepsec[maxn+5],mxdep2[maxn+5],updep2[maxn+5],qmd[maxn+5],qmd2[maxn+5],lg2[maxn+5];
int prel[maxn+5],prer[maxn+5],sufl[maxn+5],sufr[maxn+5],prewujiaoans[maxn+5],sufwujiaoans[maxn+5];
int pre_ans1[maxn+5],stmxdep[maxn+5][20],stmxdeppos[maxn+5][20],stmxdep2[maxn+5][20],Lb[maxn+5],Rb[maxn+5];
int disuv,W,dfn[maxn+5],dpre[maxn+5];
int sufyoujiaoans[maxn+5],stqingmxdep2[maxn+5][20];
struct SegmentTree 
{//线段树
    struct node 
    {
        int mxr,mxl,mx;
        node () {mxr=mxl=mx=0;}
        node (int a,int b,int c) {mxl=a,mxr=b,mx=c;}
        node operator + (const node &x) const 
        {
            node ret;
            ret.mxr=max(mxr,x.mxr);
            ret.mxl=max(mxl,x.mxl);
            ret.mx=max(mx,x.mx);
            ret.mx=max(ret.mx,mxl+x.mxr);
            return ret;
        }
    } nd[maxn*4+5];
    void upd(int p) {nd[p]=nd[p+p]+nd[p+p+1];}
    void build(int p,int l,int r) 
    {
        if (l==r) 
        {
            int u=dpre[l];
            nd[p]= {qmd[u]+dep[u],qmd[u]-dep[u],-inf};
            return ;
        }
        int mid=(l+r)>>1;
        build(p+p,l,mid);
        build(p+p+1,mid+1,r);
        upd(p);
    }
    node query(int p,int l,int r,int ql,int qr) 
    {
        if (ql>qr) return {-inf,-inf,-inf};
        if (l==ql&&r==qr) {return nd[p];}
        int mid=(l+r)>>1;
        if (qr<=mid) return query(p+p,l,mid,ql,qr);
        else if (mid<ql) return query(p+p+1,mid+1,r,ql,qr);
        else return query(p+p,l,mid,ql,mid)+query(p+p+1,mid+1,r,mid+1,qr);
    }
} T;
struct Query 
{
    int s,t,w;
    Query() {s=t=w=0;}
    Query(int a,int b,int c) {s=a,t=b,w=c;}
} Q[maxm+5];
int que[maxn+5];
void bfs()
{
    int he=1,ta=0;
    que[++ta]=1;
    while (he<=ta) 
    {
        int u=que[he++];
        bfn[u]=++btot;
        bpre[btot]=u;
        for (auto v:g[u]) 
        {
            if (bfn[v]) continue ;
            que[++ta]=v;
        }
    }
}
void trans(int &fir,int &sec,int x) 
{
    if (x<0) return ;
    if (x>=fir) sec=fir,fir=x;
    else sec=max(sec,x);
}
void dfs1(int u,int pre) 
{
    siz[u]=1;
    mxdep[u]=0;
    mxdepsec[u]=-inf;
    mxdep2[u]=0;
    int fir=-inf,sec=-inf;
    for (auto v:g[u]) 
    {
        if (v==pre) continue ;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v,u);
        trans(mxdep[u],mxdepsec[u],mxdep[v]+1);
        trans(mxdep[u],mxdepsec[u],mxdepsec[v]+1);
        siz[u]+=siz[v];
        if (siz[v]>siz[wso[u]]) wso[u]=v;
        trans(fir,sec,mxdep[v]+1);
        mxdep2[u]=max(mxdep2[u],mxdep[v]+1);
        mxdep2[u]=max(mxdep2[u],mxdep2[v]);
    }
    mxdep2[u]=max(mxdep2[u],fir+sec);
    ans=min(ans,2*(n-1)-mxdep2[u]);
}
int askmxdep(int l,int r) 
{
    if (l>r) return -inf;
    int k=lg2[r-l+1];
    return max(stmxdep[l][k],stmxdep[r-(1<<k)+1][k]);
}
int askmxdeppos(int l,int r) 
{
    if (l>r) return -inf;
    int k=lg2[r-l+1];
    int x=stmxdeppos[l][k],y=stmxdeppos[r-(1<<k)+1][k];
    if (mxdep[bpre[x]]>mxdep[bpre[y]]) return x;
    else return y;
}
int askqingmxdep2(int l,int r) 
{
    if (l>r) return -inf;
    int k=lg2[r-l+1];
    return max(stqingmxdep2[l][k],stqingmxdep2[r-(1<<k)+1][k]);
}
pair<int,int> fir_sec(int l,int r) 
{
    if (l>r) return {-inf,-inf};
    int mx=askmxdep(l,r);
    int mxpos=askmxdeppos(l,r);
    int lmx=askmxdep(l,mxpos-1),rmx=askmxdep(mxpos+1,r);
    return {mx,max(lmx,rmx)};
}
void dfs2(int u) //换根
{
    static vector<int> son;
    static vector<pair<int,int>> pre,suf;
    son.clear(),pre.clear(),suf.clear();
    for (auto v:g[u]) 
    {
        if (v==fa[u]) continue ;
        son.push_back(v);
    }
    if (son.size()==0) return ;
    pre.resize(son.size());
    suf.resize(son.size());
    int siz=son.size();
    pre[0]= {mxdep[son[0]],-inf};
    for (int i=1; i<siz; i++) 
    {
        pre[i].first=pre[i-1].first;
        pre[i].second=pre[i-1].second;
        trans(pre[i].first,pre[i].second,mxdep[son[i]]);
    }
    suf[siz-1]= {mxdep[son[siz-1]],-inf};
    for (int i=siz-2; i>=0; i--) 
    {
        suf[i].first=suf[i+1].first;
        suf[i].second=suf[i+1].second;
        trans(suf[i].first,suf[i].second,mxdep[son[i]]);
    }
    for (int i=0; i<siz; i++) 
    {
        int v=son[i];
        pair<int,int> P= {-inf,-inf},Q= {-inf,-inf};
        if (i!=0) P=pre[i-1];
        int fir=0,sec=-inf;
        if (i!=siz-1) Q=suf[i+1];
        trans(fir,sec,updep[u]+1),trans(fir,sec,P.first+2),trans(fir,sec,P.second+2),trans(fir,sec,Q.first+2),trans(fir,sec,Q.second+2);
        updep2[v]=max(updep[v],updep2[u]),updep2[v]=max(updep2[v],max(fir,fir+sec-2));
        updep[v]=max(updep[v],fir);
    }
    for (int i=0; i<siz; i++) dfs2(son[i]);
}
pair<int,int> make(pair<int,int> x) {return {x.first+1,x.second+1};}
void dfs3(int u,int tp) 
{
    top[u]=tp;
    dfn[u]=++dtot;
    dpre[dtot]=u;
    num[tp].push_back(u);
    if (wso[u]) dfs3(wso[u],tp);
    for (auto v:g[u]) 
    {
        if (v!=fa[u] && v!=wso[u]) 
        {
            dfs3(v,v);
            qing[u].push_back(v);
        }
    }
    int fir=0,sec=-inf;
    qmd[u]=0;
    qmd2[u]=0;
    for (auto v:qing[u]) 
    {
        qmd2[u]=max(qmd2[u],mxdep2[v]);
        qmd[u]=max(qmd[u],mxdep[v]+1);
        trans(fir,sec,mxdep[v]+1);
    }
    qmd2[u]=max(qmd2[u],qmd[u]);
    qmd2[u]=max(qmd2[u],fir+sec);
}
int amd2(int l,int r) 
{
    if (l>r) return -inf;
    int k=lg2[r-l+1];
    return max(stmxdep2[l][k],stmxdep2[r-(1<<k)+1][k]);
}
int qlca(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]?v:u;
}
int main() {
    freopen("patrol.in","r",stdin);
    freopen("patrol.out","w",stdout);
    cin>>n>>m;
    ans=inf;
    for (int i=2; i<=n; i++) lg2[i]=lg2[i/2]+1;
    for (int i=1; i<=m; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        u++,v++;
        if (w==1) g[u].push_back(v),g[v].push_back(u);
        else Q[++cnt]=Query(u,v,w);
    }
    bfs();
    dfs1(1,0);
    for (int i=1; i<=n; i++) {
        stmxdep[i][0]=mxdep[bpre[i]];
        stmxdeppos[i][0]=i;
        stmxdep2[i][0]=mxdep2[bpre[i]];
    }
    updep[1]=0,updepsec[1]=-inf;
    updep2[1]=0;
    dfs2(1);
    dfs3(1,1);
    for (int i=1; i<=n; i++) stqingmxdep2[i][0]=qmd2[dpre[i]];
    for (int j=1; (1<<j)<=n; j++) {
        for (int i=1; i+(1<<j)-1<=n; i++) {
            stmxdep[i][j]=max(stmxdep[i][j-1],stmxdep[i+(1<<(j-1))][j-1]);
            stmxdep2[i][j]=max(stmxdep2[i][j-1],stmxdep2[i+(1<<(j-1))][j-1]);
            stqingmxdep2[i][j]=max(stqingmxdep2[i][j-1],stqingmxdep2[i+(1<<(j-1))][j-1]);
            int x=stmxdeppos[i][j-1],y=stmxdeppos[i+(1<<(j-1))][j-1];
            if (mxdep[bpre[x]]>mxdep[bpre[y]]) stmxdeppos[i][j]=x;
            else stmxdeppos[i][j]=y;
        }
    }
    T.build(1,1,n);
    for (int i=1; i<=n; i++) {
        if (top[i]!=i) continue ;
        int siz=num[i].size();
        prel[num[i][0]]=qmd[num[i][0]]-dep[num[i][0]];
        prer[num[i][0]]=qmd[num[i][0]]+dep[num[i][0]];
        prewujiaoans[num[i][0]]=qmd2[num[i][0]];
        pre_ans1[num[i][0]]=0;
        for (int j=1; j<siz; j++) {
            prel[num[i][j]]=max(prel[num[i][j-1]],qmd[num[i][j]]-dep[num[i][j]]);
            prer[num[i][j]]=max(prer[num[i][j-1]],qmd[num[i][j]]+dep[num[i][j]]);
            prewujiaoans[num[i][j]]=max(prewujiaoans[num[i][j-1]],qmd2[num[i][j]]);
            pre_ans1[num[i][j]]=max(pre_ans1[num[i][j-1]],qmd[num[i][j]]-dep[num[i][j]]+prer[num[i][j-1]]);
        }
    }
    for (int i=1; i<=n; i++) {
        Lb[i]=inf,Rb[i]=-inf;
        for (auto v:g[i]) {
            if (v==fa[i]) continue ;
            Lb[i]=min(Lb[i],bfn[v]);
            Rb[i]=max(Lb[i],bfn[v]);
        }
    }
    int lca,disuv,prelmx;
    for (int i=1; i<=cnt; i++) {
        int s=Q[i].s,t=Q[i].t,w=Q[i].w;
        if (s==t) continue ;
        if (dep[s]<dep[t]) swap(s,t);
        lca=qlca(s,t),disuv=dep[s]+dep[t]-2*dep[lca],prelmx=0;
        if (w>=disuv) continue ;
        int tmp=2*(n-1)-disuv+w;
        static vector<pair<int,int>> nwl,nwr;
        nwl.clear();
        nwr.clear();
        int u=s,lst=-1;
        int P1=-1,P2=-1;
        while (1) {
            if (fa[u]==lca) {
                P1=u;
            }
            if (u==s) {
                ans=min(ans,tmp-mxdep2[s]);
                int mxl=mxdep[u],mxr=-inf;
                nwl.push_back({mxl,mxr});
            } else if (u!=lca) {
                int fir=0,sec=-inf;
                pair<int,int> nw=fir_sec(Lb[u],bfn[lst]-1);
                nw.first++,nw.second++;
                int len=0;
                trans(fir,sec,nw.first),trans(fir,sec,nw.second);
                nw=fir_sec(bfn[lst]+1,Rb[u]);
                nw.first++,nw.second++;
                trans(fir,sec,nw.first),trans(fir,sec,nw.second);
                len=max(len,max(fir+sec,fir)),len=max(len,amd2(Lb[u],bfn[lst]-1)),len=max(len,amd2(bfn[lst]+1,Rb[u]));
                ans=min(ans,tmp-len);
                nwl.push_back({fir+dep[s]-dep[u],fir-dep[s]+dep[u]});
            }
            if (top[u]==top[lca]) {
                if (u!=lca) {
                    P1=dpre[dfn[lca]+1];
                }
                if (dfn[lca]+1>dfn[u]-1) break ;
                SegmentTree::node dat=T.query(1,1,n,dfn[lca]+1,dfn[u]-1);
                ans=min(ans,tmp-askqingmxdep2(dfn[lca]+1,dfn[u]-1));
                ans=min(ans,tmp-dat.mx-2);
                nwl.push_back({dat.mxr+dep[s],dat.mxl-dep[s]});
                break ;
            } else {
                if (u!=top[u]) {
                    ans=min(ans,tmp-pre_ans1[fa[u]]-2);
                    ans=min(ans,tmp-prewujiaoans[fa[u]]);
                    nwl.push_back({prel[fa[u]]+dep[s],prer[fa[u]]-dep[s]});
                }
                lst=top[u];
                if (fa[top[u]]==lca) {
                    P1=top[u];
                }
                u=fa[top[u]];
            }
        }
        int fir=0,sec=-inf;
        trans(fir,sec,updep[lca]);
        u=t;
        lst=-1;
        int Llen=dep[s]-dep[lca];
        if (t!=lca) {
            while (1) {
                if (fa[u]==lca) {
                    P2=u;
                }
                if (u==t) {
                    ans=min(ans,tmp-mxdep2[t]);
                    int mxr=mxdep[u]-disuv,mxl=-inf;
                    nwr.push_back({mxl,mxr});
                } else if (u!=lca) {
                    int fir=0,sec=-inf,len=0;
                        pair<int,int> nw=fir_sec(Lb[u],bfn[lst]-1);
                        nw.first++,nw.second++;
                    trans(fir,sec,nw.first),trans(fir,sec,nw.second);
                        nw=fir_sec(bfn[lst]+1,Rb[u]);
                        nw.first++,nw.second++;
                    trans(fir,sec,nw.first),trans(fir,sec,nw.second);
                        ans=min(ans,tmp-len);
                        len=max(len,fir+sec);
                        len=max(len,fir);
                        len=max(len,amd2(Lb[u],bfn[lst]-1));
                        len=max(len,amd2(bfn[lst]+1,Rb[u]));
                    nwr.push_back({fir+dep[u]-dep[lca]+Llen,fir-dep[u]+dep[lca]-Llen});
                }
                if (top[u]==top[lca]) {
                    if (u!=lca) {
                        P2=dpre[dfn[lca]+1];
                    }
                    if (dfn[lca]+1>dfn[u]-1) break ;
                    SegmentTree::node dat=T.query(1,1,n,dfn[lca]+1,dfn[u]-1);
                    ans=min(ans,tmp-askqingmxdep2(dfn[lca]+1,dfn[u]-1));
                    ans=min(ans,tmp-dat.mx-2);
                    nwr.push_back({dat.mxl-dep[lca]+Llen,dat.mxr+dep[lca]-Llen});
                    break ;
                } else {
                    if (u!=top[u]) {
                        ans=min(ans,tmp-pre_ans1[fa[u]]-2);
                        ans=min(ans,tmp-prewujiaoans[fa[u]]);
                        nwr.push_back({prer[fa[u]]-dep[lca]+Llen,prel[fa[u]]+dep[lca]-Llen});
                    }
                    lst=top[u];
                    if (fa[top[u]]==lca) {
                        P2=top[u];
                    }
                    u=fa[top[u]];
                }
            }
        }
        static vector<pair<int,int>> ttmp;
        ttmp.clear();
        ttmp.push_back({updep[lca],-inf});
        int Len=0;
        Len=max(Len,updep2[lca]);
        fir=0,sec=-inf;
        if (P2==-1) {
            Len=max(Len,amd2(Lb[lca],bfn[P1]-1));
            Len=max(Len,amd2(bfn[P1]+1,Rb[lca]));
            ttmp.push_back(make(fir_sec(Lb[lca],bfn[P1]-1))),ttmp.push_back(make(fir_sec(bfn[P1]+1,Rb[lca])));
        } else {
            if (bfn[P1]>bfn[P2]) swap(P1,P2);
            Len=max(Len,amd2(Lb[lca],bfn[P1]-1));
            Len=max(Len,amd2(bfn[P1]+1,bfn[P2]-1));
            Len=max(Len,amd2(bfn[P2]+1,Rb[lca]));
            ttmp.push_back(make(fir_sec(Lb[lca],bfn[P1]-1))),ttmp.push_back(make(fir_sec(bfn[P1]+1,bfn[P2]-1))),ttmp.push_back(make(fir_sec(bfn[P2]+1,Rb[lca])));
        }
        for (auto t:ttmp) {
            trans(fir,sec,t.first),trans(fir,sec,t.second);
        }
        Len=max(Len,fir);
        Len=max(Len,fir+sec);
        nwl.push_back({fir+Llen,fir-Llen});
        int premxl=-inf;
        for (int i=0; i<nwl.size(); i++) {
            ans=min(ans,tmp-(premxl+nwl[i].second)-2);
            premxl=max(premxl,nwl[i].first);
        }
        for (int i=nwr.size()-1; i>=0; i--) {
            ans=min(ans,tmp-(premxl+nwr[i].second)-2);
            premxl=max(premxl,nwr[i].first);
        }
    }
    cout<<ans;
    return 0;
}