#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define Edge pair<int,LL>
#define pLL pair<LL,int>
#define To first
#define W second
using namespace std;
const int N=3e5+5;
const LL Inf=1e18;
const int B=1e6;
set<Edge>E[N],R[N];
LL D[N],Ans=Inf;
int n,m,Vis[N],TOT;
inline void Add(int x,int y,LL w){E[x].insert({y,w}),R[y].insert({x,w});}
inline void Del(int x,int y)
{
	E[x].erase(E[x].lower_bound({y,0}));
	R[y].erase(R[y].lower_bound({x,0}));
}
inline void Dij(int x)
{
	priority_queue<pLL,vector<pLL>,greater<pLL> >Q;
	Q.push({D[x]=0,x});
	vector<int>V;V.pb(x);
	
	while(!Q.empty())
	{
		int x=Q.top().W;Q.pop();
		if(Vis[x])continue;Vis[x]=1;
		for(Edge i:E[x])
		{
			TOT++;
			if(D[x]+i.W<D[i.To]&&D[x]+i.W<Ans)
				Q.push({D[i.To]=D[x]+i.W,i.To}),V.pb(i.To),TOT+=10;
		}
	}
	for(Edge i:R[x])Ans=min(Ans,D[i.To]+i.W);
	for(int i:V)D[i]=Inf,Vis[i]=0;
}
queue<int>Q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,w;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&w);
		if(x==y)Ans=min(Ans,w*1ll);
		else Add(x,y,w);
	}
	for(int i=1;i<=n;i++)Q.push(i);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		if(E[x].empty())
		{
			set<Edge>V=R[x];
			for(Edge i:V)Q.push(i.To),Del(i.To,x);
		}
		
		if(R[x].empty())
		{
			set<Edge>V=E[x];
			for(Edge i:V)Q.push(i.To),Del(x,i.To);
		}
		
		if(E[x].size()==1&&R[x].size()==1)
		{
			Edge A=*R[x].begin(),B=*E[x].begin();
			Del(A.To,x),Del(x,B.To);
			if(A.To==B.To)
			{
				Ans=min(Ans,A.W+B.W);
				Q.push(A.To);
				continue;
			}
			Add(A.To,B.To,A.W+B.W);
			Q.push(A.To),Q.push(B.To);
		}
	}
	vector<int>V;
	for(int i=1;i<=n;i++)
	{
		if(!E[i].empty())V.pb(i),D[i]=Inf;
	}
	random_shuffle(V.begin(),V.end());
	for(int i:V)
	{
		Dij(i);
		if(TOT>B)break;
	}
	if(Ans==Inf)puts("-1");
	else printf("%lld\n",Ans);
}