#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int dist[101][101];
int a[101][101];
int m,n;
const int INF=1e8;
int ans=INF;
/*void floyd_oringin()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
}
}
}
}
}*/
void floyd_o()
{
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,dist[i][j]+a[i][k]+a[k][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
}
}
void floyd()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
continue;
}
for(int k=1;k<=n;k++)
{
if(dist[i][j]!=INF&&dist[i][k]!=INF&&dist[k][j]!=INF)
{
ans=min(ans,dist[i][j]+a[i][k]+a[k][j]);
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

}
}
}
}
int main ()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dist[i][j]=INF;
a[i][j]=INF;
}
}
for(int i=1;i<=m;i++)
{
int x;
int y;
int z;
scanf("%d%d",&x,&y);
scanf("%d",&z);
if(dist[x][y]<z)
{
continue;
}
dist[x][y]=z;
dist[y][x]=dist[x][y];
a[x][y]=dist[x][y];
a[y][x]=dist[y][x];
}
floyd();
if(ans==INF)
{
printf("No solution.\n");
continue;
}
printf("%d\n",ans);
ans=INF;
}
return 0;
}