#include<bits/stdc++.h>
using namespace std;

const int M=1e5+10;
int n,m;
int deg[M];
bool cmp(int a,int b){
	return deg[a]>deg[b]||(deg[a]==deg[b]&&a<b);
}
int nxt[M],to[M],hd[M],val[M],ecnt;
int nxt2[M],to2[M],hd2[M],val2[M],ecnt2;
void Add(int a,int b,int c){
	nxt[++ecnt]=hd[a];
	to[hd[a]=ecnt]=b;
	val[ecnt]=c;

	nxt2[++ecnt2]=hd2[b];
	to2[hd2[b]=ecnt2]=a;
	val2[ecnt2]=c;
}
struct node{
	int b,c,v;
};
vector<node>G;
bool cmp1(node a,node b){
	return a.b<b.b;
}
struct Tree{
	int mx[M<<2];
	void upd(int x,int v,int L=1,int R=n,int p=1){
		if(L==R){
			mx[p]=max(mx[p],v);
			return ;
		}
		int mid=(L+R)>>1;
		if(x<=mid)upd(x,v,L,mid,p<<1);
		else upd(x,v,mid+1,R,p<<1|1);
		mx[p]=max(mx[p<<1],mx[p<<1|1]);
	}
	void set(int x,int L=1,int R=n,int p=1){
		mx[p]=0;
		if(L==R)return ;
		int mid=(L+R)>>1;
		if(x<=mid)set(x,L,mid,p<<1);
		else set(x,mid+1,R,p<<1|1);
	}
	int qry(int l,int r,int L=1,int R=n,int p=1){
		if(l>r)return 0;
		if(L==l&&r==R)return mx[p];
		int mid=(L+R)>>1;
		if(r<=mid)return qry(l,r,L,mid,p<<1);
		else if(l>mid)return qry(l,r,mid+1,R,p<<1|1);
		return max(qry(l,mid,L,mid,p<<1),
				qry(mid+1,r,mid+1,R,p<<1|1));
	}
}Tr;
struct edge{
	int a,b,c;
}E[M];
int id[M],v[M];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		deg[a]++,deg[b]++;
		E[i]=(edge){a,b,c};
	}
	for(int i=1;i<=n;++i)id[i]=i;
	sort(id+1,id+n+1,cmp);
	for(int i=1;i<=m;++i){
		auto [a,b,c]=E[i];
		if(deg[a]>deg[b])Add(a,b,c);
		else if(deg[a]==deg[b]){
			if(a<b)Add(a,b,c);
			else Add(b,a,c);
		}else Add(b,a,c);
	}
	int ans=0;
	for(int k=1;k<=n;++k){
		const int x=id[k];
		for(int i=hd[x];i;i=nxt[i]){
			int y=to[i];
			v[y]=val[i];
		}
		for(int i=hd[x];i;i=nxt[i]){
			int y=to[i];
			for(int j=hd[y];j;j=nxt[j]){
				int z=to[j];
				if(v[z])
					G.push_back((node){min(y,z),max(y,z),v[y]+v[z]+val[j]});
			}//zheng+zheng
		}
		for(int i=hd[x];i;i=nxt[i]){
			int y=to[i];
			v[y]=0;
		}

		for(int i=hd2[x];i;i=nxt2[i]){
			int y=to2[i];
			v[y]=val2[i];
		}
		for(int i=hd2[x];i;i=nxt2[i]){
			int y=to2[i];
			for(int j=hd2[y];j;j=nxt2[j]){
				int z=to2[j];
				if(v[z])
					G.push_back((node){min(y,z),max(y,z),v[y]+v[z]+val2[j]});
			}

		}//fan+fan
		for(int i=hd[x];i;i=nxt[i]){
			int y=to[i];
			for(int j=hd2[y];j;j=nxt2[j]){
				int z=to2[j];
				if(v[z])
					G.push_back((node){min(y,z),max(y,z),val[i]+v[z]+val2[j]});
			}
		}//zheng+fan
		for(int i=hd2[x];i;i=nxt2[i]){
			int y=to2[i];
			v[y]=0;
		}
	//	for(auto t:G){
	//		printf("%d-%d-%d\n",x,t.b,t.c);
	//	}
		for(int j=0,t=0;j<(int)G.size();j=t){
			while(t<(int)G.size()&&G[j].b==G[t].b)
				t++;
			for(int k=j;k<t;++k){
				int tmp=0;
				tmp=max(tmp,Tr.qry(1,G[k].b-1));
				tmp=max(tmp,Tr.qry(G[k].b+1,G[k].c-1));
				tmp=max(tmp,Tr.qry(G[k].c+1,n));
				if(tmp)ans=max(ans,tmp+G[k].v);
			}
			for(int k=j;k<t;++k)
				Tr.upd(G[k].c,G[k].v);
		}
		for(int j=0;j<(int)G.size();++j)
			Tr.set(G[j].c);
		G.clear();
	}
	printf("%d\n",ans==0?-1:ans);
	return 0;
}