#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
int const MAX=4e5+10;
int ru[MAX],chu[MAX];
vector<pr> V[MAX],V2[MAX];
int del[MAX],in[MAX];
vector<pr> E[MAX],E2[MAX];
int fan[MAX];
int vis[5005],dis[5005];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		V[u].push_back({v,w});
		V2[v].push_back({u,w});
		chu[u]++;
		ru[v]++;
	}
	queue<int> shan;
	for(int i=1;i<=n;i++){
		if(ru[i]==1&&chu[i]==1)shan.push(i),in[i]=true;
		if(!ru[i]||!chu[i])shan.push(i),in[i]=true;
	}
	int ans=0x3f3f3f3f3f3f3f3f;
	while(!shan.empty()){
		//if(shan.size()>n)return -1;
		//cerr<<shan.size()<<"\n";
		int tp=shan.front();
		shan.pop();
		if(!ru[tp]||!chu[tp]){
			del[tp]=1;
			if(chu[tp]){
				for(auto q:V[tp]){
					int it=q.fi;
					if(del[it])continue;
					ru[it]--;
					if(ru[it]==0||chu[it]+ru[it]==2){
						if(!in[it]){
							shan.push(it);
							in[it]=true;
						}
					}
				}
			}
			if(ru[tp]){
				for(auto q:V2[tp]){
					int it=q.fi;
					if(del[it])continue;
					chu[it]--;
					if(chu[it]==0||chu[it]+ru[it]==2){
						if(!in[it]){
							shan.push(it);
							in[it]=true;
						}
					}
				}
			}
		}
		if(ru[tp]==chu[tp]&&chu[tp]==1){
			int s,t,w1=0,w2=0;
			for(auto q:V[tp]){
				int it=q.fi;
				if(del[it])continue;
				t=it;
				w1=q.se;
				break;
			}
			for(auto q:V2[tp]){
				int it=q.fi;
				if(del[it])continue;
				s=it;
				w2=q.se;
				break;
			}
			if(s==t&&t==tp){
				ans=min(ans,w1);
				del[tp]=true;
				continue;
			}
			del[tp]=true;
			V[s].push_back({t,w1+w2});
			V2[t].push_back({s,w1+w2});
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(!del[i])fan[i]=++cnt;
	}
	for(int i=1;i<=n;i++){
		if(!del[i]){
			//cerr<<i<<"\n";
			for(auto it:V[i]){
				if(!del[it.fi]){
					E[fan[i]].push_back({fan[it.fi],it.se});
				}
			}
			for(auto it:V2[i]){
				if(!del[it.fi]){
					E2[fan[i]].push_back({fan[it.fi],it.se});
				}
			}
		}
	}
	//cerr<<" "<<cnt<<"\n";
	//for(int i=1;i<=cnt;i++){
	//	for(auto it:E2[i])cerr<<i<<" "<<it.fi<<" "<<it.se<<"\n";
	//}
	for(int i=1;i<=cnt;i++){
		priority_queue<pr,vector<pr>,greater<pr>> Q;
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		dis[i]=0;
		Q.push({0,i});
		while(!Q.empty()){
			int tp=Q.top().se;
			Q.pop();
			if(vis[tp])break;
			vis[tp]=true;
			for(auto it:E[tp]){
				if(vis[it.fi])continue;
				if(it.se+dis[tp]<dis[it.fi]){
					dis[it.fi]=it.se+dis[tp];
					Q.push({dis[it.fi],it.fi});
				}
			}
		}
		for(auto it:E2[i]){
			ans=min(ans,dis[it.fi]+it.se);
		}
	}
	cout<<(ans==0x3f3f3f3f3f3f3f3f?-1:ans);
	return 0;
}