#include <bits/stdc++.h>
using namespace std;
#define int long long
struct qwq{
	int x, cost;
	bool operator < (const qwq &b) const {return (cost > b.cost);}
};
int n, m, x[5005], y[5005], z[5005], g[105][105], id[105][105];
int ans = 1e18, vis[105], dis[105];
int dijk(int idx){
	int s = x[idx], t = y[idx];
	priority_queue<qwq> q; 
	q.push({s, 0});
	for (int i = 1;i <= n;i++) dis[i] = 1e17; 
	memset(vis, 0, sizeof(vis));
	dis[s] = 0;
	while (!q.empty()){
		int x = q.top().x; q.pop();
		if (vis[x]) continue;
		vis[x] = 1;
		for (int i = 1;i <= n;i++){
			if (g[x][i] < 1e18 && id[x][i] != idx){
				int cost = g[x][i];
				if (dis[i] > dis[x] + cost){
					dis[i] = dis[x] + cost;
					q.push({i, dis[i]});
				}
			}
		}
	} return (dis[t] > 1e16 ? -1ll : dis[t]);
} signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(g, 0x3f, sizeof(g));
	cin >> n >> m;
	for (int i = 1;i <= m;i++){
		cin >> x[i] >> y[i] >> z[i];
		g[x[i]][y[i]] = g[y[i]][x[i]] = min(g[x[i]][y[i]], z[i]);
		id[x[i]][y[i]] = id[y[i]][x[i]] = i;
	} for (int i = 1;i <= m;i++){
		int dist = dijk(i);
		if (dist != -1ll) ans = min(ans, dist + z[i]);
	} cout << ((ans >= 1e16) ? "No solution." : to_string(ans));
	return 0;
}