#include<iostream> #include<cstdio> using namespace std; int f[109][109]; int c[109]; bool b[109]; int maxn=0x7fffff; int main() { int m,n; int x,y,z; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=maxn; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); f[x][y]=f[y][x]=z; } for(int i=1;i<=n;i++) c[i]=f[1][i]; c[1]=0; b[1]=1; for(int i=1;i<=n-1;i++) { int minn=maxn; int k=0; for(int j=1;j<=n;j++) if(b[j]==0&&c[j]<minn) { minn=c[j]; k=j; } if(k==0)break; b[k]=1; for(int j=1;j<=n;j++) if(c[k]+f[k][j]<c[j]) c[j]=c[k]+f[k][j]; } int p=0; for(int i=1;i<=n;i++) p=max(p,c[i]); printf("%d",p); return 0; }
