1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long ll;

 4 const int N=200100;

 5 int n,m,x,y,z,tot,p,q,head[N];

 6 ll ans,sum,dis[N];

 7 int nxt[N<<1],to[N<<1],w[N<<1];

 8

 9 void add(int x,int y,int z){

10     nxt[++tot]=head[x];

11     head[x]=tot;

12     to[tot]=y;

13     w[tot]=z;

14 }

15

16 void dfs1(int u,int fa,ll s){

17     if(s>sum) sum=s,p=u;

18     for(int i=head[u];i;i=nxt[i]){

19         int v=to[i];

20         if(v==fa) continue;

21         dfs1(v,u,s+w[i]);

22     }

23 }

24

25 void dfs2(int u,int fa,ll s){

26     if(s>ans) ans=s,q=u;

27     for(int i=head[u];i;i=nxt[i]){

28         int v=to[i];

29         if(v==fa) continue;

30         dfs2(v,u,s+w[i]);

31     }

32 }

33

34 void dfs3(int u,int fa,ll s){

35     dis[u]=s;

36     for(int i=head[u];i;i=nxt[i]){

37         int v=to[i];

38         if(v==fa) continue;

39         dfs3(v,u,s+w[i]);

40     }

41 }

42

43 void dfs4(int u,int fa,ll s){

44     dis[u]=min(dis[u],s);//在到p的距离和到q的距离中选择更近的那一个

45     for(int i=head[u];i;i=nxt[i]){

46         int v=to[i];

47         if(v==fa) continue;

48         dfs4(v,u,s+w[i]);

49     }

50 }

51

52 int main(){

53     scanf("%d%d",&n,&m);

54     for(int i=1;i<=m;i++){

55         scanf("%d%d%d",&x,&y,&z);

56         add(x,y,z);add(y,x,z);

57

58     }

59     dfs1(1,0,0);//求直径的一个端点p

60     dfs2(p,0,0);//求直径的另一端点q，和直径长度ans

61     dfs3(p,0,0);//枚举每个点到p的距离

62     dfs4(q,0,0);//枚举每个点到q的距离

63     sum=0;

64     for(int i=1;i<=n;i++)

65         sum=max(sum,dis[i]);

66     printf("%lld\n",sum+ans);

67     return 0;

68 }