RT，总是输出 1321730049。

#include <iostream>

using namespace std;

#define INF 1e18

int n, m;
int G[105][105];
long long f[105][105]; 

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j) G[i][j] = f[i][j] = INF;
	for (int i = 1; i <= m; i++) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		G[u][v] = min(G[u][v], w);
		G[v][u] = min(G[v][u], w);
		f[u][v] = min(f[u][v], 1LL * w);
		f[v][u] = min(f[v][u], 1LL * w);
	}
	long long ans = INF;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i < k; i++)
			for (int j = i + 1; j < k; j++)
				if (G[i][k] != INF && G[j][k] != INF)
					ans = min(ans, G[i][k] + G[j][k] + f[i][j]);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	}
	if (ans == INF) {
		puts("No solution.");
		return;
	}
	printf("%lld\n", ans);
}

int main() { solve(); }