#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
unordered_set<int> s;
set<pair<int, ll > >e[N],e2[N];
bool pd[N];
int d1[N],d2[N],n,m;
bool isdel(int p){
	return d1[p]==0||d2[p]==0||(d1[p]==1&&d2[p]==1);
}
set<pair<pair<int, int>, ll> > E;//边集
void erase(int x,int y,ll z){
	E.erase({{x,y},z});
}
void del(int p){
	pd[p]=1;
	if(d1[p]==1&&d2[p]==1){
		auto x=*e[p].begin();
		auto y=*e2[p].begin();
		int u=y.first,v=x.first;
		ll w=x.first+y.first;
		E.insert({{u,v},w});
		e[u].insert({v,w});
		e2[v].insert({u,w});
		e[p].clear();
		e[u].erase({p,y.second});
		erase(u,p,y.second);
		e2[v].erase({p,x.second});
		erase(p,v,x.second);
		s.erase(p);
		return;
		//u->p->v
	}
	for(auto it:e[p]){
		int t=it.first;
		ll w=it.second;
		d1[t]--;
		if(isdel(t))s.insert(t);
		e[t].erase({p,w});
		erase(p,t,w);
	}
	for(auto it:e2[p]){
		int t=it.first;
		ll w=it.second;
		d2[t]--;
		if(isdel(t))s.insert(t);
		e[t].erase({p,w});
		erase(t,p,w);
	}
	e[p].clear(),e2[p].clear();
	s.erase(p);
}
namespace solve{
	const int N=3005;
	ll dis[N][N];
	priority_queue<pair<ll, int> > q;
	vector<pair<int, ll> > e[N];
	void add(int x,int y,ll z){
		e[x].push_back({y,z});
//		cout<<x<<" "<<y<<" "<<z<<endl;
	}
	void solve(ll *dis,int s){
		for(int i=1;i<=n;++i)
			dis[i]=1e18;
		q.push({0,s}),dis[s]=0;
		while(!q.empty()){
			int p=q.top().second;
			ll v=-q.top().first;
			q.pop();
			if(dis[p]>v)continue;
			for(auto it:e[p]){
				int t=it.first;ll v=it.second;
				if(dis[t]>dis[p]+v){
					dis[t]=dis[p]+v;
					q.push({-dis[t],t});
				}
			}
		}
	}
	ll work(){
		for(int i=1;i<=n;++i)
			solve(dis[i],i);
		ll ans=1e18;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if(i!=j)ans=min(ans,dis[i][j]+dis[j][i]);
		return ans;
	}
}
int mp[N],tot;
int main(){
	cin>>n>>m;int x,y,z;
	ll ans=1e18;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		if(x==y){
			ans=min(ans,(ll)z);
			continue;
		}
		if(E.find({{x,y},z})!=E.end())
			continue;
		e[x].insert({y,z});
		e2[y].insert({x,z});
		d1[y]++,d2[x]++;
		E.insert({{x,y},z});
	}
	for(int i=1;i<=n;++i)
		if(isdel(i))s.insert(i);
	while(!s.empty()){
		int p=*s.begin();
		del(p);
		s.erase(p);
	}
	for(auto it:E){
		int x=it.first.first,y=it.first.second;
		ll z=it.second;
		if(!mp[x])mp[x]=++tot;
		if(!mp[y])mp[y]=++tot;
		x=mp[x],y=mp[y];
		solve::add(x,y,z);
	}
	n=tot;
	ans=min(ans,solve::work());
	if(ans>1e17)puts("-1");
	else cout<<ans;
}