POJ - 1985

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

#define ri register int
#define u int
#define NN 500005
#define MM 500005

namespace all {

    u N,M,ans,mxl[NN];

    u cnt,h[NN];
    struct node {
        u to,next,va;
    } a[MM<<1];
    inline void add(const u &x,const u &y,const u &z) {
        a[++cnt].next=h[x],a[cnt].to=y,a[cnt].va=z,h[x]=cnt;
    }

    void dfs(const u &x,const u &prt) {
        for(ri i(h[x]); i; i=a[i].next) {
            u _y(a[i].to);
            if(_y^prt) {
                dfs(_y,x);
                ans=std::max(ans,mxl[x]+mxl[_y]+a[i].va);
                mxl[x]=std::max(mxl[_y]+a[i].va,mxl[x]);
            }
        }
    }

    inline void solve() {
        scanf("%d%d",&N,&M);
        for(ri i(1); i<=M; ++i) {
            u _a,_b,_c;
            char _s;
            scanf("%d%d%d %c",&_a,&_b,&_c,&_s);//毒瘤读入，输入的字母对此题没有卵用 
            add(_a,_b,_c),add(_b,_a,_c);
        }
        dfs(1,0);
        printf("%d",ans);
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    all::solve();

}