#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int f[105][105],in[105][105];
signed main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			f[i][j]=100000000;
		}
		f[i][i]=0;
	}
	for (int i=1;i<=m;i++)
	{
		int u,w,v;
		cin>>u>>w>>v;
		in[w][u]=in[u][w]=f[w][u]=f[u][w]=min(f[u][w],v);
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			for (int k=1;k<=n;k++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
		if (f[i][i]<0)
		{
			cout<<"No solution.";
			return 0;
		}
	}
	int ans=100000000;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=i;j++)
		{
			for (int k=j+1;k<=i;k++)
			{
				ans=min(ans,f[j][k]+in[j][i]+in[i][j]);
			}
		}
	}

	cout<<ans;
	return 0;
}