Решение "Обход Графа"

void Floyd_Warshall(int n, vector<vector<int>>& out_d)
{
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (out_d[i][k] < INT32_MAX && out_d[k][j] < INT32_MAX && out_d[i][j] > out_d[i][k] + out_d[k][j])
                {
                    out_d[i][j] = out_d[i][k] + out_d[k][j];
                }
}

int main() {
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    int n, m;
    int sum = 0;
    cin >> n >> m;
    vector<vector<int>> d(n, vector<int>(n, INT32_MAX));
    vector<int> cnt(n, 0);
    int u, v, w;
    for (int i = 0; i < n; i++)
        d[i][i] = 0;
    while (m--)
    {
        cin >> u >> v >> w;
        u--, v--;
        d[u][v] = d[v][u] = min(d[v][u], w);
        sum += w;
        cnt[u]++;
        cnt[v]++;
    }
    if (cnt[0] == 0 && sum != 0)
    {
        cout << -1 << endl;
        return 0;
    }

    Floyd_Warshall(n, d);
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (d[i][j] == INT32_MAX && cnt[i] && cnt[j])
            {
                cout << -1 << endl;
                return 0;
            }

    vector<int> p_odd;
    for (int i = 0; i < n; i++)
        if (cnt[i] & 1)
            p_odd.push_back(i);
    vector<int> dp(1 << p_odd.size(), INT32_MAX);

    for (int i = 0; i + 1 < p_odd.size(); i++)
        for (int j = i + 1; j < p_odd.size(); j++)
            dp[(1 << i) + (1 << j)] = d[p_odd[i]][p_odd[j]];

    dp[0] = 0;
    for (int a = 5; a < dp.size(); a++)
    {
        if ((__popcnt(a) & 1))
            continue;

        int c = (a - 1) & a;
        while (c)
        {
            if (!(__popcnt(c) & 1))
            {
                int b = a ^ c;
                dp[a] = min(dp[a], dp[c] + dp[b]);
            }
            c = (c - 1) & a;
        }
    }
    cout << sum + dp.back();//dp[dp.size()-1]
    return 0;
}