#include<bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;

const int maxn = 100005;

int n,m;
vector< pair<int,int> >V[maxn],E[maxn];
int d[maxn],p[maxn],pos[maxn];
inline bool cmp(const int x,const int y)
{
	return d[x]<d[y];
}

int v[maxn];
struct node
{
	int mx[3],id[3];
	node()
	{
		memset(mx,-1,sizeof mx);
		memset(id,0,sizeof id);
	}
	void upd(int c,int i)
	{
		if(id[0]==i) mx[0]=max(mx[0],c);
		else if(id[1]==i) mx[1]=max(mx[1],c);
		else if(id[2]==i) mx[2]=max(mx[2],c);
		else
		{
			mx[2]=c,id[2]=i;
		}
		
		if(mx[1]<mx[2]) swap(mx[1],mx[2]),swap(id[1],id[2]);
		if(mx[0]<mx[1]) swap(mx[0],mx[1]),swap(id[0],id[1]);
		if(mx[1]<mx[2]) swap(mx[1],mx[2]),swap(id[1],id[2]);
	}
	int query(int x,int y)
	{
		for(int i=0;i<=2;i++)
		{
			if(id[i]!=x && id[i]!=y) return mx[i];
		}
		assert(0);
	}
}val[maxn];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c; cin>>x>>y>>c;
		V[x].emplace_back(y,c);
		V[y].emplace_back(x,c);
		d[x]++,d[y]++;
	}
	
	for(int i=1;i<=n;i++) p[i]=i;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++) pos[p[i]]=i;
	
	for(int x=1;x<=n;x++) for(auto [y,c]:V[x])
	{
		if(pos[y]>pos[x])
			E[pos[x]].emplace_back(pos[y],c);
	}
	
	int ans=-1;
	for(int i=1;i<=n;i++)
	{
		for(auto [y,c]:E[i]) v[y]=c;
		
		for(auto [y,c]:E[i])
		{
			for(auto [yy,cc]:E[y]) if(v[yy]>0)
			{
				int tc;
				
				tc= val[i].query(y,yy);
				if(tc!=-1) ans=max(ans, v[yy]+c+cc+tc );
				
				tc= val[y].query(i,yy);
				if(tc!=-1) ans=max(ans, v[yy]+c+cc+tc );
				
				tc= val[yy].query(i,y);
				if(tc!=-1) ans=max(ans, v[yy]+c+cc+tc );
			}
			
			for(auto [yy,cc]:E[y]) if(v[yy]>0)
			{
				val[i].upd(v[yy]+c+cc, yy);
			}
		}
		
		for(auto [y,c]:E[i])
		{
			for(auto [yy,cc]:E[y]) if(v[yy]>0)
			{
				val[y].upd(v[yy]+c+cc,yy);
				
				val[yy].upd(v[yy]+c+cc,y);
			}
		}
		
		for(auto [y,c]:E[i]) v[y]=0;
	}
	cout<<ans<<endl;
	
	return 0;
}

/*
6 9
1 2 3
2 3 1
3 4 2
4 5 1
3 5 7
2 5 2
1 5 3
4 6 2
5 6 1

*/