#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,fa[300005],sp[300005],ord[300005],tot,tg[300005];
vector<pair<int,int> >v[300005],v2[300005],to[300005];
int dis[10005],vis[10005],ans,InF=1e18,I;
struct Node{
	int x,y,w;
};
vector<Node>e;
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void dfs(int x,int y){
	if(sp[x]&&ord[x]!=I){
//		cout<<I<<"->"<<ord[x]<<endl;
		to[ord[x]].push_back({I,y});
		v2[I].push_back({ord[x],y});
		return ;
	}
	for(auto i:v[x]){
		dfs(i.first,y+i.second);
	}
	return ;
}
mt19937 rng(time(0));
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ans=InF;
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i,tg[i]=-1;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		if(x==y){
			ans=min(ans,w);
			continue;
		}
		if(find(x)!=find(y)){
			fa[find(x)]=find(y);
			v[x].push_back({y,w});
		}
		else{
			sp[x]=sp[y]=1;
			e.push_back({x,y,w});
		}
	}
	
	for(int i=1;i<=n;i++)
		if(rng()%1000==0)sp[i]=1;
	for(int i=1;i<=n;i++){
		if(sp[i])ord[i]=++tot;
	}
	for(int i=1;i<=n;i++){
		if(sp[i])I=ord[i],dfs(i,0);
	}
	for(auto i:e){
		int x=i.x,y=i.y,w=i.w;
//		cout<<x<<' '<<y<<' '<<w<<endl;
		v2[ord[x]].push_back({ord[y],w});
		to[ord[y]].push_back({ord[x],w});
	}
	for(int s=1;s<=tot;s++){
		priority_queue<pair<int,int> >pq;
		pq.push({0,s});
		memset(vis,0,sizeof(vis));
		memset(dis,0x3f,sizeof(dis));
		dis[s]=0;
		while(!pq.empty()){
			int x=pq.top().second;pq.pop();
			if(vis[x])continue;
			vis[x]=1;
			if(x<s)continue;
			if(dis[x]>ans)continue;
			for(auto i:v2[x]){
				int y=i.first,w=i.second;
				if(dis[y]>dis[x]+w){
					dis[y]=dis[x]+w;
					pq.push({-dis[y],y});
				}
			}
		}
		for(auto i:to[s]){
			int t=i.first;
//			cout<<s<<' '<<t<<":"<<i.second<<' '<<dis[t]<<endl;
			ans=min(ans,i.second+dis[t]);
		}
	}
	cout<<(ans>=1e16?-1:ans)<<endl;
	return 0;
}