#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pii pair<int,ll>
#define node pair<ll,int>
using namespace std;
const int maxn=3e5+5,maxf=3e3+5;
vector<pii>e0[maxn],e1[maxn];
vector<pii>e[maxn];
int p[maxn];
// array<array<ll,maxf>,maxf>dis;
array<ll,maxn>dis;
vector<int>pos;
ll ans=1e18;
void dij(int x){
	priority_queue<node,vector<node>,greater<node>>q;
	q.push({0,x});
	for(auto u:pos)dis[u]=1e18;
	dis[x]=0;
	while(!q.empty()){
		int now=q.top().second;
		ll d=q.top().first;
		q.pop();
		if(dis[now]<d)continue;
		for(auto u:e[now]){
			if(dis[u.first]>u.second+d){
				dis[u.first]=u.second+d;
				q.push({dis[u.first],u.first});
				
			}
			if(u.first==x)ans=min(ans,u.second+d);
		}
	}
	// ans=min(ans,dis[x]);
}
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(u==v){
			ans=min(ans,1ll*w);
			continue;
		}
		e0[u].push_back({v,w});
		e1[v].push_back({u,w});
	}
	int cnt0=0,cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(e0[i].size()+e1[i].size()<3)cnt2++;
		if(e0[i].empty()||e1[i].empty()){
			p[i]=1;
			cnt0++;
		}
		if(e0[i].size()==1&&e1[i].size()==1){
			// e[e1[i][0].first].push_back({e0[i][0].first,e0[i][0].second+e1[i][0].second});
			p[i]=1;
			cnt1++;
		}
	}
	for(int i=1;i<=n;i++){
		if(!p[i]){
			for(auto u:e0[i]){
				int flag=0,t=u.first;
				ll d=u.second;
				while(p[t]){
					if(e0[t].empty()){flag=1;break;}
					d+=e0[t][0].second;
					t=e0[t][0].first;
				}
				if(flag)continue;
				e[i].push_back({t,d});
			}
			pos.push_back(i);
		}
	}
	if(pos.size()>3010){
		cout<<cnt0<<" "<<cnt1<<" "<<cnt2<<" "<<pos.size()<<"\n";
		return;
	}
	for(int i=1;i<=n;i++){
		if(!p[i]){
			dij(i);
		}
	}
	if(ans==1e18)cout<<"-1\n";
	else cout<<ans<<"\n";

}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
/*
n*3/2<=n+1500
m>=n*3/2
n<=3000
*/