#include<bits/stdc++.h>
#define ll long long
#define int long long
#define int_128 __int128
#define lowbit(x) (x&(-x))
using namespace std;
inline int read() {
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s;
}
inline void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
//int ans;
int n,m;
int dp[505][505];
int ans=0x3f3f3f3f3f3f3f3f;
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(dp,0x3f,sizeof dp);
	for(int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		dp[x][y]=min(dp[x][y],z);
		dp[y][x]=min(dp[y][x],z);
	}
	for(int k=2;k<=n;k++){
		for(int i=2;i<=n;i++){
			for(int j=2;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ans=min(ans,dp[1][i]+dp[i][j]+dp[j][1]);
		}
	}
	if(ans!=0x3f3f3f3f3f3f3f3f) cout<<ans;
	else cout<<-1;
	cout<<endl;
	return 0;
}