#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;
	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});
			}
		}
	}
	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});
	}
	for(int i=1;i<=n;i++){
		if(e0[i].empty()||e1[i].empty()){
			p[i]=1;
		}
		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;
		}
	}
	for(int i=1;i<=n;i++){
		for(auto u:e0[i]){
			if(!p[i]&&!p[u.first]){
				e[i].push_back(u);
			}
		}
		if(!p[i])pos.push_back(i);
	}
	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
*/