#include<bits/stdc++.h>
#define int long long
using namespace std;
int _u,_v,_w;
int n,m;
struct sb{
	int v,w;
};
enum {
	SMXSB=114514,
	SMX_DONT_LOVE_HUTAO=1086
};
int dis[SMX_DONT_LOVE_HUTAO][SMX_DONT_LOVE_HUTAO];
int minn=1e13;
int w[186][186];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i-j)dis[i][j]=w[i][j]=1e13;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>_u>>_v>>_w;
		dis[_u][_v]=min(dis[_u][_v],_w);
		dis[_v][_u]=min(dis[_v][_u],_w);
		w[_v][_u]=min(w[_u][_v],_w);
		w[_u][_v]=min(w[_v][_u],_w);
	}
	for(int k=2;k<=n;k++){
		for(int i=1;i<k;i++){
			for(int j=i+1;j<k;j++){
				minn=min(minn,dis[i][j]+w[i][k]+w[k][j]);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][k-1]+dis[k-1][j]);
				dis[j][i]=dis[i][j];
			}
		}
	}
	if(minn==1e13)cout<<"No solution.";
	else cout<<minn;
}