#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
set<int> G[400400];
ll f[400400],g[400400];
int u[400400],v[400400],tot;
map<int,int> E[400400];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		ll w;
		cin>>u>>v>>w;
		if(E[u].count(v))
		{
			int e=E[u][v];
			if(::u[e]==u)
				f[e]=min(f[e],w);
			else
				g[e]=min(g[e],w);
			G[u].insert(e);
			G[v].insert(e);
		}
		else
		{
			int e=++tot;
			f[e]=w;
			::u[e]=u;
			::v[e]=v;
			E[u][v]=E[v][u]=e;
			G[u].insert(e);
			G[v].insert(e);
		}
	}
	queue<int> q;
	for(int i=1;i<=n;i++)
		if(G[i].size()<=2)
			q.push(i);
	while(!q.empty())
	{
		int x=q.front();
		if(!G[x].size()) break;
		if(G[x].size()==1)
		{
			int e=*G[x].begin();
			int y=u[e]+v[e]-x;
			G[x].clear();
			G[y].erase(e);
			if(G[y].size()==2)
				q.push(y);
		}
		else
		{
			int e1=*G[x].begin();
			G[x].erase(e1);
			int e2=*G[x].begin();
			G[x].erase(e2);
			int y1=u[e1]+v[e1]-x;
			int y2=u[e2]+v[e2]-x;
			G[y2].erase(e2);
			if(u[e1]!=y1)
			{
				swap(u[e1],v[e1]);
				swap(f[e1],g[e1]);
			}
			if(u[e2]!=x)
			{
				swap(u[e2],v[e2]);
				swap(f[e2],g[e2]);
			}
			f[e1]+=f[e2];
			g[e2]+=g[e2];
			G[y2].insert(e1);
			v[e1]=y2;
		}
	}
	vector<int> vertex,edge;
	for(int i=1;i<=n;i++)
		if(G[i].size())
			vertex.push_back(i);
	for(auto x:vertex)
		for(auto e:G[x])
			if(x==u[e])
				edge.push_back(e);
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(auto ban:edge)
	{
		static ll dist[3030];
		memset(dist,0x3f,sizeof(dist));
		priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		dist[v[ban]]=0;
		pq.emplace(0,v[ban]);
		while(!pq.empty())
		{
			int x=pq.top().second;
			ll d=pq.top().first;
			pq.pop();
			if(dist[x]!=d)
				continue;
			for(auto e:G[x])
			{
				int y=u[e]+v[e]-x;
				ll nd=d+(u[e]==x?f[e]:g[e]);
				if(nd<dist[y])
				{
					dist[y]=nd;
					pq.emplace(nd,y);
				}
			}
		}
		ans=min(ans,f[ban]+dist[u[ban]]);
	}
	for(auto e:edge)
		swap(f[e],g[e]);
	for(auto ban:edge)
	{
		static ll dist[3030];
		memset(dist,0x3f,sizeof(dist));
		priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		dist[v[ban]]=0;
		pq.emplace(0,v[ban]);
		while(!pq.empty())
		{
			int x=pq.top().second;
			ll d=pq.top().first;
			pq.pop();
			if(dist[x]!=d)
				continue;
			for(auto e:G[x])
			{
				int y=u[e]+v[e]-x;
				ll nd=d+(u[e]==x?f[e]:g[e]);
				if(nd<dist[y])
				{
					dist[y]=nd;
					pq.emplace(nd,y);
				}
			}
		}
		ans=min(ans,f[ban]+dist[u[ban]]);
	}
	if(ans==0x3f3f3f3f3f3f3f3f)
	{
		cout<<"-1\n";
		return 0;
	}
	cout<<ans<<endl;
	return 0;
}