#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int main()
{
int n,m,i,j,k,dis[110][110];
while(cin>>n>>m)
{
int Min=INT_MAX;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=INT_MAX;
for(i=1;i<=m;i++)
{
int temp1,temp2;
cin>>temp1>>temp2;
cin>>dis[temp1][temp2];
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j&&dis[k][j]<INT_MAX&&dis[i][k]<INT_MAX)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(dis[i][j]<INT_MAX&&dis[j][i]<INT_MAX)
dis[i][j]+=dis[j][i];
else
dis[i][j]=INT_MAX;
}
Min=min(Min,*min_element(dis[i]+1,dis[i]+1+n));
}
if(Min<INT_MAX)
cout<<Min<<endl;
else
cout<<"No solution."<<endl;
}
}