#include<fstream.h>
#define inf -1000
ifstream f("royfloyd.in");
int a[100][100],n,m,d[50][50];
void citire_graf()
	{
	int x,y,c;
	f>>n>>m;
	for(int i=1;i<=n;i++)
		{
		for(int j=1;j<=n;j++)
			a[i][j]=inf;
			a[i][i]=0;
			}
		for(i=1;i<=m;i++)
			{f>>x>>y>>c;
			a[x][y]=c;
			}
		f.close();
	}
void r_floyd()
	{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(a[i][k]!=inf&&a[k][j]!=inf)
					if(a[i][j]<a[i][k]+a[k][j])
						a[i][j]=a[i][k]+a[k][j];
	}
int diam()
	{
	int max=a[1][1];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			max=a[i][j];
	return max;
	}
int main()
	{
	ofstream g("royfloyd.out");
	citire_graf();
	r_floyd();
	g<<diam();
	g.close();
	return 0;
	}