void solve() {
    int n, m;
    cin >> n >> m;
    vector e(n + 1, vector<pii>());
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    const int inf = 1e9;
    int res = inf;
    auto wk = [&] (int u, int v, int w) {
        if (u == v) return;
        vector<int> dis(n + 1, inf);
        dis[u] = 0;
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push({0, u});
        vector<bool> visi(n + 1);
        while (q.size()) {
            auto [D, x] = q.top(); q.pop();
            if (visi[x]) continue;
            visi[x] = 1;
            for (auto [y, w] : e[x]) {
                if ((x == u && y == v) || (x == v && y == u)) continue;
                if (dis[y] > dis[x] + w) {
                    dis[y] = dis[x] + w;
                    q.push({dis[y], y});
                }
            }
        }
        // db(dis[v], u, v, w);
        res = min(res, dis[v] + w);
    };

    for (int u = 1; u <= n; u++) for (auto [v, w] : e[u]) {
        wk(u, v, w);
    }
    if (res == inf) {
        cout << "No solution.";
    } else {
        cout << res;
    }
}