#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=3005;
typedef long long ll;
const ll inf=1e18;
int n,m,id[N],ct;
bool dl[N],vis[M];
set<pair<int,ll> >oe[N],ie[N];
vector<pair<int,ll> >e[M],g[M];
queue<int>dq;
priority_queue<pair<ll,int> >q;
ll ans=inf,dis[M];
void check(int x){
	if(dl[x])return;
	if(oe[x].empty()||ie[x].empty()||oe[x].size()+ie[x].size()<3){
		dq.push(x);
		dl[x]=true;
	}
}
void dijk(int S){
	for(int i=1;i<=ct;++i)dis[i]=inf,vis[i]=false;
	dis[S]=0;
	q.push({0,S});
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(auto [x,y]:e[u])if(dis[x]>dis[u]+y){
			dis[x]=dis[u]+y;
			q.push({-dis[x],x});
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		if(x==y){
			ans=min(ans,(ll)z);
			continue;
		}
		oe[x].insert({y,z}),ie[y].insert({x,z});
	}
	for(int i=1;i<=n;++i)check(i);
	while(!dq.empty()){
		int u=dq.front();
		dq.pop();
		if(!oe[u].empty()&&!ie[u].empty()){
			auto [x1,y1]=*oe[u].begin();
			auto [x2,y2]=*ie[u].begin();
			ie[x1].erase({u,y1});
			oe[x2].erase({u,y2});
			if(x1==x2)ans=min(ans,y1+y2);
			else ie[x1].insert({x2,y1+y2}),oe[x2].insert({x1,y1+y2});
			check(x1),check(x2);
		}else{
			for(auto [x,y]:ie[u]){
				oe[x].erase({u,y});
				check(x);
			}
			for(auto [x,y]:oe[u]){
				ie[x].erase({u,y});
				check(x);
			}
		}
	}
	for(int i=1;i<=n;++i)if(!dl[i])id[i]=++ct;
	for(int i=1;i<=n;++i)if(!dl[i]){
		for(auto [x,y]:oe[i])e[id[i]].push_back({id[x],y});
		for(auto [x,y]:ie[i])g[id[i]].push_back({id[x],y});
	}
	for(int i=1;i<=ct;++i){
		dijk(i);
		for(auto [x,y]:g[i])ans=min(ans,y+dis[x]);
	}
	if(ans==inf)puts("-1");
	else printf("%lld\n",ans);
	return 0;
}