#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]);
}
int vis[maxn],inst[maxn];
ll dist[maxn];
bool cmp(pii x,pii y){
	return x.second<y.second;
}
void dfs(int x){
	if(vis[x])return;
	inst[x]=1;
	vis[x]=1;
	for(auto u:e0[x]){
		if(inst[u.first]){
			ans=min(ans,dist[x]-dist[u.first]+u.second);
			continue;
		}
		if(!vis[u.first]){
			dist[u.first]=u.second+dist[x];
			dfs(u.first);
		}
	}
	inst[x]=0;
}
int deg0[maxn],deg1[maxn];
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});
		deg0[u]++;
		deg1[v]++;
	}
	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;
		}
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		dfs(i);
		if((deg0[i]==0||deg1[i]==0||deg0[i]+deg1[i]==1)&&!p[i]){
			p[i]=1;
			q.push(i);
		}
	}
	while(!q.empty()){
		int now=q.front();q.pop();
		for(auto u:e0[now]){
			int i=u.first;
			deg1[i]--;
			if((deg0[i]==0||deg1[i]==0||deg0[i]+deg1[i]==1)&&!p[i]){
				p[i]=1;
				q.push(i);
			}
		}
		for(auto u:e1[now]){
			int i=u.first;
			deg0[i]--;
			if((deg0[i]==0||deg1[i]==0||deg0[i]+deg1[i]==1)&&!p[i]){
				p[i]=1;
				q.push(i);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!p[i]){
			map<int,int>mp;
			sort(e0[i].begin(),e0[i].end(),cmp);
			for(auto u:e0[i]){
				int flag=0,t=u.first;
				if(mp[t])continue;
				mp[t]=1;
				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);
		}
	}
	for(int i=1;i<=n;i++){
		if(!p[i]){
			dij(i);
		}
	}
	if(ans==1e18)cout<<"-1\n\n\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
*/