#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=150;
int n,m,k,s,t,c[N],tot;
int ans=0x3f3f3f3f;
int b[N][N],f[N][N];
int main(){
	cin>>n>>m;
	memset(b,0x3f,sizeof(b));
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=m;++i){
		cin>>s>>t>>k;
		b[s][t]=b[t][s]=f[s][t]=f[t][s]=min(b[s][t],k);
	}
	for (int k=1;k<=n;++k){
		for (int i=1;i<k;++i)
			for (int j=i+1;j<k;++j){
				if (f[i][j]==0x3f3f3f3f) continue;
				ans=min(ans,f[i][j]+b[i][k]+b[k][j]);
			}
		for (int i=1;i<=n;++i)
			for (int j=i+1;j<=n;++j)
				f[j][i]=f[i][j]=min(f[i][j],f[i][k]+f[k][j]);;
	}
	if (ans==0x3f3f3f3f) cout<<"No solution.";
	else cout<<ans<<endl;
	 
}