#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define N 100010
#define fi first
#define se second
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int rd() {
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
	return res*f;
}
int n,m,deg[N];
int sz;
unordered_map<int,int>G[N];
unordered_map<int,int> :: iterator it1,it2;
struct node {
	int x,y,val;
};
vector<node>st;
bool cmp(node x,node y) {
	return x.val>y.val;
}
int big[N];
int ans=-1;
void work() {
	sort(st.begin(),st.end(),cmp);
	rep(i,0,min(5,(int)st.size()-1)) {
		rep(j,i+1,(int) st.size()-1) {
			if(st[i].val+st[j].val<=ans) break;
			if(st[i].x!=st[j].x&&st[i].x!=st[j].y&&st[i].y!=st[j].x&&st[i].y!=st[j].y) ans=max(ans,st[i].val+st[j].val);
		}
	}
}
int main() {
//	freopen("A.in","r",stdin);
	n=rd(),m=rd();
	sz=sqrt(m);
	for(int i=1,u,v,w;i<=m;i++) {
		u=rd(),v=rd(),w=rd();
		G[u][v]=G[v][u]=w;
		deg[u]++,deg[v]++;
	}
	rep(i,1,n) if(deg[i]>=sz) big[++big[0]]=i;
	rep(i,1,n) if(deg[i]<sz&&deg[i]>=2) {
		it1=G[i].begin();
		while(it1!=G[i].end()) {
			it2=it1,it2++;
			while(it2!=G[i].end()) {
				if(G[it1->fi].count(it2->fi)) {
					int tmp=it1->se+it2->se+G[it1->fi][it2->fi];
					st.push_back((node) {it1->fi,it2->fi,tmp});
				}
				it2++;
			}
			it1++;
		}
		work();
		st.clear();
	}
	rep(i,1,big[0]) {
		rep(j,i+1,big[0]) rep(k,j+1,big[0]) {
			if(G[big[i]].count(big[j])&&G[big[i]].count(big[k])&&G[big[j]].count(big[k])) {
				int tmp=G[big[i]][big[j]]+G[big[i]][big[k]]+G[big[j]][big[k]];
				st.push_back((node) {big[j],big[k],tmp});
			}
		}
		for(auto it:G[big[i]]) if(deg[it.fi]<sz) {
			for(auto IT:G[it.fi]) if(IT.fi!=big[i]&&G[big[i]].count(IT.fi)) {
				st.push_back((node) {big[i],it.fi,IT.fi});
			}
		}
		work(),st.clear();
	}
	printf("%d",ans);
	return 0;  
}