#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans = 0x7fffffff,u,v,w,g[1010][1010],dis[1010][1010];
int main() {
	scanf("%d%d",&n,&m);
	memset(dis,0x3f,sizeof(dis));
	for (int i = 1;i <= m;i ++) {
		scanf("%lld%lld%lld",&u,&v,&w);
		dis[u][v] = dis[v][u] = g[u][v] = g[v][u] = w;
	}
	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] + g[i][k] + g[k][j]);
		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 != 0x7fffffff) printf("%lld\n",ans);
	else printf("No solution.\n");
	return 0;
}