#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#define inf 1000000
int v[101][101],loop[101][101];
using namespace std;
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
int a,b,c;
int ans=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j) v[i][j]=loop[i][j]=0;
else v[i][j]=loop[i][j]=inf;
}
for(int i=1;i<=m;i++){
scanf("%d %d %d",&a,&b,&c);
// if(c<v[a][b])
v[b][a]=loop[a][b]=v[a][b]=loop[b][a]=c; <---就是这里,如果注释掉了就过了，可不应该是取最小值吗
}//去重边
for(int k=1;k<=n;k++){
//最小环问题，枚举的点放在最外层循环，且先对环用K进行更新，再更新边，避免环用K走了两次, 且v更新，loop为原来的输入值
//o，另外枚举的i>j都必须比k小
for(int i=1;i<k;i++)
for(int j=1;j<i;j++){
ans=min(ans,v[i][j]+loop[i][k]+loop[k][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
v[i][j]=min(v[i][j],v[i][k]+v[k][j]);
}
if(ans==inf) printf("No solution.\n") ;
else printf("%d\n",ans);
}
return 0;
}