Й

#include <bits/stdc++.h>

/*

8 15
1 2 1
1 4 8
1 8 5
2 3 6
2 4 3
2 5 2
2 6 2
2 7 3
2 8 4
3 4 2
3 5 3
4 6 4
5 6 7
6 7 4
7 8 5

*/

using namespace std;

long v, r, a[1001][1001], q, w, e, smax = 1000001, sum, n, p[1001], pr[1001], t, re[1001], g;

void H(long x)
{
    p[x] = 1;
    n++;

    for (int i = 1; i <= v; i++)
        if (p[i] == 0 && a[x][i] > 0)
        {
            pr[i] = x;
            sum += a[x][i];
            H(i);
            sum -= a[x][i];
        }
    if (n == v && a[x][1] > 0)
    {
        if (sum + a[x][1] < smax)
            smax = sum + a[x][1];
        g = x;
        for (t = 0; t < v; t++)
        {
            re[t] = g;
            g = pr[g];
        }
    }
    p[x] = 0;
    n--;
}

int main()
{
    fstream fin("in.txt");
    fin >> v >> r;
    for (int i = 1; i <= r; i++)
    {
        fin >> q >> w >> e;
        a[q][w] = e;
        a[w][q] = e;
    }
    H(1);
    cout << smax << endl;
    for (int i = 0; i < t; i++)
    {
        cout << re[i] << " ";
    }
    fin.close();
    return 0;
}