#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=300010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,m,ans=inf;
set<pii> e[maxn],g[maxn];
queue<int> q;
int dis[maxn];
bool vis[maxn];
priority_queue<pii> qq;
vector<pii> fr[maxn],bk[maxn];
vector<int> p;
void work(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		e[u].insert({v,w}),g[v].insert({u,w});
		if(u==v)ans=min(ans,w);
	}
	for(int u=1;u<=n;u++)if(!e[u].size()||!g[u].size())q.push(u);
	while(!q.empty()){
		int u=q.front();q.pop();
		if(e[u].size()){
			for(auto[v,w]:e[u]){
				g[v].erase({u,w});
				if(!e[v].size()||!g[v].size())q.push(v);
			}
			e[u].clear();
		}
		else{
			for(auto[v,w]:g[u]){
				e[v].erase({u,w});
				if(!e[v].size()||!g[v].size())q.push(v);
			}
			g[u].clear();
		}
	}
	for(int u=1;u<=n;u++)if(e[u].size()==1&&g[u].size()==1){
		auto[v,w1]=*e[u].begin();
		auto[w,w2]=*g[u].begin();
		g[v].erase({u,w1}),e[w].erase({u,w2});
		g[v].insert({w,w1+w2}),e[w].insert({v,w1+w2});
	}
	for(int u=1;u<=n;u++)if(e[u].size()&&g[u].size()){
		p.pb(u);
		for(auto[v,w]:e[u])bk[u].pb({v,w});
		for(auto[v,w]:g[u])fr[u].pb({v,w});
	}
	for(int s:p){
		for(int i:p)dis[i]=inf,vis[i]=0;dis[s]=0;qq.push({0,s});
		while(!qq.empty()){
			int u=qq.top().se;qq.pop();
			if(vis[u])continue;vis[u]=1;
			for(auto[v,w]:bk[u]){
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w,qq.push({-dis[v],v});
				}
			}
		}
		for(auto[v,w]:fr[s])ans=min(ans,dis[v]+w);
	}
	if(ans==inf)puts("-1");
	else printf("%lld\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}