#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF=999999999;
const int N=1005;
int ans=INF,e[N][N],dis[N][N],n,m;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=INF;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
e[i][j]=INF;
e[i][i]=0;

}
int a,b,c;
for(int i=1;i<=m;i++)

{
scanf("%d%d%d",&a,&b,&c);
e[a][b]=e[b][a]=min(e[a][b],c);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=e[i][j];
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
ans=min(ans,dis[i][j]+e[i][k]+e[j][k]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
if(ans>=INF) printf("No solution.\n");
else printf("%d\n",ans);

}
return 0;
}