#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
int n,m;
const int N=5005;
bool vis[N];
int maqp[N][N];
int dis[N];
void disq()
{
	int x,y,k;
	memset(dis,0x3f,sizeof dis);
	
	for(int i=1;i<=n;i++)
	 dis[i] = maqp[1][i];
	 
	dis[1]=0;
	vis[1]=1;
	for(int i=1;i<=n;i++)
	{
		int minn=INF;
		for(int j=1;j<=n;j++)
		{
			if(!vis[i] && dis[j]<minn)
			{
				minn=dis[j];
				k=j;
			}
		}
		vis[k]=1;
		for(int j=1;j<=n;j++)
		    dis[j]=min(dis[j],dis[k]+maqp[k][j]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==INF)  
		{
			cout<<-1;
			return;
		}
		ans=max(ans,dis[i]);
	}
	cout<<ans;
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		maqp[a][b]=c;
		maqp[b][a]=c;
	}
	disq();
	return 0;
}