#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=3e5+5;
map<int,ll>I[N],O[N];
int n,m,deg[N];
const ll INF=1e18;

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read(),m=read();ll res=INF;
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		if(u==v)cmin(res,(ll)w);
		if(O[u].find(v)==O[u].end())O[u][v]=w;
		else if(O[u][v]>w)O[u][v]=w;
		if(I[v].find(u)==I[v].end())I[v][u]=w;
		else if(I[v][u]>w)I[v][u]=w;
		deg[u]++,deg[v]++;
	}
	
	queue<int>q;
	vector<int>del(n+1),inq(n+1);
	for(int i=1;i<=n;i++)if(deg[i]<=2)q.push(i),inq[i]=1;
	
	while(q.size()){
		int x=q.front();q.pop(),del[x]=1;
//		cout<<"del x = "<<x<<" deg = "<<deg[x]<<endl;
//		cout<<"In edges = ";for(auto [y,w]:I[x])cout<<"("<<y<<","<<w<<") ";puts("");
//		cout<<"Out edges = ";for(auto [y,w]:O[x])cout<<"("<<y<<","<<w<<") ";puts("");
		if(deg[x]==0)continue;
		if(deg[x]==1){
			if(O[x].size()==1){
				auto [y,w]=*O[x].begin();deg[y]--,I[y].erase(x),deg[x]--;
				if(deg[y]<=2&&(!inq[y]))q.push(y),inq[y]=1;
			}
			else if(I[x].size()==1){
				auto [y,w]=*I[x].begin();deg[y]--,O[y].erase(x),deg[x]--;
				if(deg[y]<=2&&(!inq[y]))q.push(y),inq[y]=1;
			}
			continue;
		}
		if(I[x].size()==2){
			for(auto [y,w]:I[x]){
				deg[y]--,deg[x]--,O[y].erase(x);
				if(deg[y]<=2&&(!inq[y]))q.push(y),inq[y]=1;
			}
		}
		else if(O[x].size()==2){
			for(auto [y,w]:O[x]){
				deg[y]--,deg[x]--,I[y].erase(x);
				if(deg[y]<=2&&(!inq[y]))q.push(y),inq[y]=1;
			}
		}
		else{
			auto [y,wy]=*I[x].begin();auto [z,wz]=*O[x].begin(); // y -> x -> z
//			cout<<y<<" -> "<<x<<" -> "<<z<<endl;
			if(y==z){
				deg[x]-=2,deg[y]-=2,O[y].erase(x),I[y].erase(x);
				cmin(res,wy+wz);
			}
			else if(O[y].find(z)!=O[y].end()){
				if(O[y][z]>wy+wz)O[y][z]=wy+wz;
				O[y].erase(x),I[z].erase(x),deg[y]--,deg[z]--;
				if(deg[y]<=2&&(!inq[y]))q.push(y),inq[y]=1;
				if(deg[z]<=2&&(!inq[z]))q.push(z),inq[z]=1;
			}
			else O[y][z]=I[z][y]=wy+wz,O[y].erase(x),I[z].erase(x);
		}
//		cout<<"now deg = ";for(int i=1;i<=n;i++)cout<<deg[i]<<" ";puts("");
	}
	
//	cout<<"del = ";for(int i=1;i<=n;i++)cout<<del[i]<<" ";puts("");
	
	int ncnt=0;vector<int>id(n+1);
	for(int i=1;i<=n;i++)if(!del[i])id[i]=++ncnt;
	if(ncnt==0){
		if(res<INF)cout<<res<<endl;
		else puts("-1");
		return 0;
	}
	vector<vector<pair<int,ll> > >G(ncnt+1);
	for(int i=1;i<=n;i++)if(!del[i]){
		for(auto [y,w]:O[i])if(!del[y])G[id[i]].emplace_back(mk(id[y],w));
	}
	
	auto calc=[&](int s){
		vector<ll>dis(n+1,INF);
		vector<int>vis(n+1,0);
		priority_queue<pair<ll,int> >Q;
		
		Q.push(mk(0ll,s)),dis[s]=0;
		while(Q.size()){
			auto [d,u]=Q.top();Q.pop();
			if(vis[u])continue;vis[u]=1;
			for(auto [v,w]:G[u]){
				if(v<s)continue;
				if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,Q.push(mk(-dis[v],v));
			}
		}
		
		ll ans=INF;
		for(int i=s+1;i<=n;i++)for(auto [j,w]:G[i])if(j==s)cmin(ans,w+dis[i]);
		return ans;
	};
	
	for(int i=1;i<=n;i++)cmin(res,calc(i));
	if(res>=INF)puts("-1");
	else cout<<res<<endl;

	return 0;
}