#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,q[105][105],a,b,c,i,j,k,f[105][105],edge=100000000;
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i){
for(j=1;j<=n;++j){
q[i][j]=100000000;
f[i][j]=100000000;
}
q[i][i]=0;
}
for(i=1;i<=m;++i){
scanf("%d%d%d",&a,&b,&c);
if(c<q[b][a]){
f[i][j]=f[j][i]=c;
q[a][b]=c;
q[b][a]=c;}
}
for(k=1;k<=n;++k){
for(i=1;i<=k-1;++i)
for(j=1;j<=i-1;++j){
edge=min(edge,q[j][k]+f[i][j]+q[k][i]);
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
if(edge!=100000000)
printf("%d",edge);
else printf("No solution.");
return 0;
}