#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 600000

int i,j,k,n,m,t,fa[N+50],in[N+50],dfn[N+50],it;
ll res=1e18;

vector<pair<int,int> > v2[N+50];
vector<tuple<int,int,int> > bian,v[N+50];
set<int> s0,s1;
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
ll f[N+50];
ll dep[N+50],g[N+50],dep2[N+50];

struct SB{
	int i,j,k,n;
	int f[N+50][21],l2[N+50];
	int _get(int l,int r){
		return (dfn[l]<dfn[r]?l:r);
	}
	void init(int nn){
		n=nn;
		for(i=1;i<=20;i++)for(j=1;j+(1<<i)-1<=n;j++)f[j][i]=_get(f[j][i-1],f[j+(1<<(i-1))][i-1]);
	}
	int lca(int l,int r){
		if(l==r)return l;
		l=dfn[l]; r=dfn[r]; if(l>r)swap(l,r);
		l++; int k=l2[r-l+1];
		return _get(f[l][k],f[r-(1<<k)+1][k]);
	}
}sb;

void dfs(int x,int fa){
	if(dfn[x])exit(3);
	dfn[x]=++it; sb.f[it][0]=fa;
	//cout<<"nmsl "<<x<<' '<<fa<<' '<<it<<endl;
	for(auto [i,j,k]:v[x])if(i!=fa){
		g[i]=g[x]+k;
		dep[i]=dep[x]+j;
		dep2[i]=dep2[x]+1;
		dfs(i,x);
	}
}

bool cmp(int x,int y){return dfn[x]<dfn[y];}

void fuck0(){
	vector<int> tmp={1},tmp2;
	for(auto i:s0)tmp.push_back(i);
	sort(tmp.begin(),tmp.end(),cmp);
	int sz=tmp.size(),i;
	for(int i=0;i<sz;i++){
		//cout<<"CNM "<<tmp[i]<<' '<<tmp[i+1]<<' '<<sb.lca(tmp[i],tmp[i+1])<<endl;
		tmp2.push_back(tmp[i]);
		if(i!=sz-1)tmp2.push_back(sb.lca(tmp[i],tmp[i+1]));
	}
	sort(tmp2.begin(),tmp2.end(),cmp);
	tmp2.erase(unique(tmp2.begin(),tmp2.end()),tmp2.end());
	//cout<<"NMSL"<<endl; for(auto i:tmp2){cout<<i<<' ';}cout<<endl;
	for(auto i:tmp2)s1.insert(i);
	
	sz=tmp2.size();
	for(i=0;i<sz-1;i++){
		int x=tmp2[i],y=tmp2[i+1];
		x=sb.lca(x,y);
		//cout<<"NMSL "<<x<<' '<<y<<' '<<g[x]<<' '<<g[y]<<' '<<dep2[x]<<' '<<dep2[y]<<endl;
		if(g[y]-g[x]==0){
			
			v2[y].push_back({x,dep[y]-dep[x]});
		}
		if(g[y]-g[x]==dep2[y]-dep2[x]){
			//cout<<"CNM "<<x<<' '<<y<<' '<<dep[y]-dep[x]<<endl;
			v2[x].push_back({y,dep[y]-dep[x]});
		}
	}
}

ll fuck(ll st,ll ed){
	for(auto i:s1){
		//cout<<"CNMNMSL "<<i<<endl;
		f[i]=1e18;
	}
	priority_queue<pair<ll,ll> > q;
	q.push({0,st});
	while(!q.empty()){
		auto [w,id]=q.top(); q.pop(); w=-w;
		//cout<<"NMSL "<<st<<' '<<id<<' '<<w<<' '<<f[id]<<endl;
		if(f[id]<=w)continue;
		f[id]=w;
		for(auto [i,j]:v2[id])if(f[i]>w+j){
			q.push({-(w+j),i});
		}
	}
	return f[ed];
}

int main(){
	for(i=2;i<=N;i++)sb.l2[i]=sb.l2[i/2]+1;
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)fa[i]=i;
	for(i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(find(x)==find(y)){
			v2[x].push_back({y,z});
			bian.push_back({x,y,z});
			s0.insert(x); s0.insert(y);
			
			//cout<<"nmsl "<<x<<' '<<y<<' '<<z<<endl;
			continue;
		}
		//cout<<"nmsl "<<x<<' '<<y<<' '<<z<<endl;
		fa[find(x)]=find(y);
		v[x].push_back({y,z,1});
		v[y].push_back({x,z,0});
		in[y]++;
	}
	dfs(1,0);
	sb.init(n);
	fuck0();
	if(bian.size()>2000)return 1;
	int NMSL=0;
	for(i=1;i<=n;i++){
		NMSL+=v2[i].size();
	}
	if(NMSL>10000)return 2;
	for(auto [l,r,w]:bian){
		res=min(res,fuck(r,l)+w);
	}
	if(res>1e17)res=-1;
	cout<<res;
}