// Wrongri-La Shower

#include <cstdio>
#include <random>
#include <array>
#include <algorithm>
#include <functional>
#include <vector>

int N, M;
int list[3000][3];

int point = 0;
std::vector<int> v, best;

template <typename T>
std::function<T()> randomR(
    T lb, // ^ 下限
    T ub  // ^ 上限
){
    std::random_device rd;
    std::array<T, 10> seeds;
    std::generate(seeds.begin(), seeds.end(), std::ref(rd));

    std::seed_seq seq(seeds.begin(), seeds.end());
    return std::bind(std::uniform_int_distribution<T>(lb, ub),
                     std::mt19937(seq));
}

int evaluate(){
    int point = 0;
    
    for(int i=0;i<M;i++){
        int a, b;
        for(int j=0;j<N;j++){
            if(v[j] == list[i][0]){
                a = j;
            }else if(v[j] == list[i][1]){
                b = j;
            }
        }

        if(a < b){point += list[i][2];}
    }

    return point;
}

std::function<int()> choose;

void change(){
    int a = choose(), b = choose();
    if(a == b){return;}

    std::vector<int> u(v.begin(), v.end());
    std::swap(v[a], v[b]);
    int p = evaluate();
    if(p > point){
        point = p;
        std::copy(v.begin(), v.end(), best.begin());
    }else{
        v = std::move(u);
    }
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i=0;i<M;i++){
        scanf("%d %d %d", &list[i][0], &list[i][1], &list[i][2]);
    }

    v.resize(N);
    best.resize(N);    
    choose = randomR(0, N-1);
    
    std::iota(v.begin(), v.end(), 0);
    std::random_shuffle(v.begin(), v.end());
    point = evaluate();
    std::copy(v.begin(), v.end(), best.begin());
    
    while (clock() / (double)(CLOCKS_PER_SEC) < 4.50){
        change();
    }

    printf("%d\n", point);
    for(int i=0;i<best.size();i++){
        printf("%d%c", best[i], " \n"[i+1==best.size()]);
    }
    puts("252521");
}