#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,ans=-1;
int u[N],v[N],w[N],deg[N],vis[N];
struct node{
	int to,w;
};
vector<node> E[N],e[N];
struct nn{
	int x,y,w;
}Rem[N];
int cmp(nn a,nn b){
	return a.x<b.x;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		E[u[i]].push_back({v[i],w[i]});
		E[v[i]].push_back({u[i],w[i]});
		deg[u[i]]++,deg[v[i]]++;
	}
	for(int i=1;i<=m;i++){
		if(deg[u[i]]>deg[v[i]]||(deg[u[i]]==deg[v[i]]&&u[i]>v[i]))swap(u[i],v[i]);
		e[u[i]].push_back({v[i],w[i]});
	}
	for(int i=1;i<=n;i++){
		int cnt=0,tp1=0,tp2=0,tp3=0,val1=-1e9,val2=-1e9,val3=-1e9;
		for(auto j:E[i]) vis[j.to]=j.w;
		for(auto j:E[i]){
			int x=j.to;
			for(auto k:e[x]){
				int y=k.to;
				if(vis[y]) Rem[++cnt]={x,y,j.w+k.w+vis[y]};
			}
		}
		for(auto j:E[i]) vis[j.to]=0;
		sort(Rem+1,Rem+1+cnt,cmp);
		for(int j=1;j<=cnt;){			
			int t=j;
			while(1){
				if(Rem[j].x!=tp1&&Rem[j].y!=tp1) ans=max(ans,Rem[j].w+val1);
				if(Rem[j].x!=tp2&&Rem[j].y!=tp2) ans=max(ans,Rem[j].w+val2);
				if(Rem[j].x!=tp3&&Rem[j].y!=tp3) ans=max(ans,Rem[j].w+val3);
				if(Rem[j].x!=Rem[j+1].x) break;
				j++;
			}
			swap(j,t);
			while(j<=t){
				if(Rem[j].y==tp1) val1=max(val1,Rem[j].w);
				else if(Rem[j].y==tp2){
					val2=max(val2,Rem[j].w);
					if(val2>val1) swap(tp1,tp2),swap(val1,val2);
				}
				else if(Rem[j].y==tp3){
					val3=max(val3,Rem[j].w);
					if(val3>val2) swap(tp2,tp3),swap(val2,val3);
					if(val2>val1) swap(tp1,tp2),swap(val1,val2);
				}
				else if(Rem[j].w>val1){
					tp3=tp2,val3=val2;
					tp2=tp1,val2=val1;
					tp1=Rem[j].y,val1=Rem[j].w;
				}
				else if(Rem[j].w>val2){
					tp3=tp2,val3=val2;
					tp2=Rem[j].y,val2=Rem[j].w;
				}
				else if(Rem[j].w>val3) tp3=Rem[j].y,val3=Rem[j].w;
				j++;
			}
		}
	}
	cout<<ans;
	return 0;
}