#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=3e5+1505;
constexpr long long LINF{0x3f3f3f3f3f3f3f3fll};
int n,m;
long long ans{LINF};
struct W{long long a,b;};	// 正走、反走的贡献
inline W operator+(W a,W b){
	auto t=W{a.a+b.a,a.b+b.b};
	t.a=min(t.a,LINF),t.b=min(t.b,LINF);
	return t;
}
map<int,W> g[N];
bool del[N];
int id[N],idc,idp[N];
long long dis[N];
vector<pair<int,ll> > gnew[N],grev[N];
inline void adde(int u,int v,W w){
	auto p=g[u].insert(make_pair(v,w));
	if(!p.second){
		auto it=p.first;
		it->second.a=min(it->second.a,w.a),
		it->second.b=min(it->second.b,w.b);
	}
}
void dij(int s){
	using Q=pair<long long,int>;
	static bool vst[N];
	for(int i{1};i<=idc;++i){
		dis[idp[i]]=LINF;
		vst[idp[i]]=false;
	}
	priority_queue<Q,vector<Q>,greater<Q>> q;
	q.emplace(dis[s]=0ll,s);
	while(!q.empty()){
		int u{q.top().second}; q.pop();
		if(vst[u]) continue; else vst[u]=true;
		for(auto e:gnew[u]){
			int v{e.first};long long w{e.second};
			if(dis[u]+w<dis[v]) q.emplace(dis[v]=dis[u]+w,v);
		}
	}
}
inline void bf(){
	for(int i{1};i<=idc;++i){
		int u{idp[i]};
		dij(u);
		for(auto e:grev[u]){
			int v{e.first}; ll w{e.second};
			ans=min(ans,w+dis[v]);
		}
	}
}
void simplify(){
	static bool inq[N];
	queue<int> q;
	for(int i{1};i<=n;++i)
		if(g[i].size()<=2u) q.emplace(i);
	while(!q.empty()){
		int u{q.front()}; q.pop(); inq[u]=false;
		if(del[u]) continue;
		del[u]=true;
		if(g[u].size()==1u){
			auto e=*g[u].begin();
			int v{e.first};W w{e.second};
			ans=min(ans,w.a+w.b);
			g[v].erase(u);
			if(!inq[v]&&g[v].size()<=2u) q.emplace(v),inq[v]=true;
		}
		else if(g[u].size()==2u){
			auto e1=*g[u].begin(),e2=*prev(g[u].end());
			int v1{e1.first},v2{e2.first};
			W w1{e1.second},w2{e2.second};
			swap(w1.a,w1.b);
			del[u]=true;
			g[v1].erase(u),g[v2].erase(u);
			ans=min(ans,w1.a+w1.b);
			ans=min(ans,w2.a+w2.b);
			W w12{w1+w2},w21{w2+w1};
			swap(w21.a,w21.b);
			adde(v1,v2,w12),adde(v2,v1,w21);
			if(!inq[v1]&&g[v1].size()<=2u) q.emplace(v1);
			if(!inq[v2]&&g[v2].size()<=2u) q.emplace(v2);
		}
		g[u].clear();
	}
	for(int i{1};i<=n;++i)
		if(!del[i])
			idp[id[i]=++idc]=i;
	int ec{0};
	fprintf(stderr,"idc=%d\n",idc);
	for(int i{1};i<=idc;++i){
		int u{idp[i]};
		for(auto e:g[u]){
			int v{e.first}; W w{e.second};
			if(w.a<LINF) gnew[u].emplace_back(v,w.a),++ec;
			if(w.b<LINF) grev[u].emplace_back(v,w.b);
		}
	}
	fprintf(stderr,"ec=%d\n",ec);
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i{1};i<=m;++i){
		int u,v;ll w; cin>>u>>v>>w;
		if(u==v) ans=min(ans,1ll*w);
		else adde(u,v,W{w,LINF}),adde(v,u,W{LINF,w});
	}
	simplify();
	bf();
	if(ans==LINF) ans=-1ll;
	cout<<ans<<'\n';
	return 0;
}