#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define RN 250005

#define IMAX 0x3f3f3f3f
#define IMIN (~IMAX)

typedef int I;
typedef char C;
typedef long long L;

#define SWAP(T, a, b) { T t = a; a = b; b = t; }

// Pools

typedef struct
{
    I nxt;
    I to;
    I cap;
    L cost;
}
Network;

Network net_pool[RN * 2];
I       ncnt = 1;

#define nnode(x) net_pool[x]
#define nnxt(x)  nnode(x).nxt
#define nto(x)   nnode(x).to
#define ncap(x)  nnode(x).cap
#define ncost(x) nnode(x).cost

// Network Simplex

I head[RN], fa[RN], fe[RN], mark[RN], cycle[RN];
L pi[RN];
I ti;

static inline void addEdge(I u, I v, I f, L c)
{
    nnode(++ncnt) = (Network){head[u], v, f, c};
    head[u] = ncnt;
    nnode(++ncnt) = (Network){head[v], u, 0, -c};
    head[v] = ncnt;
}

void initTree(I x)
{
    mark[x] = 1;
    for (I i = head[x]; i; i = nnxt(i))
    {
        I v = nto(i);
        if (!mark[v])
        {
            fa[v] = x, fe[v] = i;
            initTree(v);
        }
    }
}

L phi(I x)
{
    if (mark[x] == ti) return pi[x];
    return mark[x] = ti, pi[x] = phi(fa[x]) - ncost(fe[x]);
}

void pushFlow(I e, I root, L *cost)
{
    I pen = nto(e ^ 1), lca = nto(e);
    while (pen != root)   mark[pen] = ti + 1,  pen = fa[pen];
    while (lca != root && mark[lca] != ti + 1) lca = fa[lca];
    
    I e2 = 0, f = ncap(e), path = 2, clen = 0;
    for (I i = nto(e ^ 1); i != lca; i = fa[i])
    {
        cycle[++clen] = fe[i];
        if (ncap(fe[i]) < f) f = ncap(fe[e2 = i] ^ (path = 0)); 
    }
    for (I i = nto(e); i != lca; i = fa[i])
    {
        cycle[++clen] = fe[i] ^ 1;
        if (ncap(fe[i] ^ 1) <= f) f = ncap(fe[e2 = i] ^ (path = 1));
    }
    cycle[++clen] = e;
    
    for (I i = 1; i <= clen; i++)
    {
        ncap(cycle[i])     -= f;
        ncap(cycle[i] ^ 1) += f;
        *cost += 1ll * f * ncost(cycle[i]);
    }
    if (path == 2) return;
    
    I laste = e ^ path, last = nto(laste), cur = nto(laste ^ 1);
    while (last != e2)
    {
        laste ^= 1;
        SWAP(I, laste, fe[cur]);
        SWAP(I, last, fa[cur]);
        SWAP(I, last, cur);
    }
}

I simplex(I st, I ed, L *cost)
{
    addEdge(ed, st, IMAX, 0x3f3f3f3f3f3f);
    *cost = 0;
    initTree(ed);
    mark[ed] = ti = 2;
    for (I i = 3, pre = 2; i != pre; i = i == ncnt ? 2 : i + 1)
    {
        if (ncap(i) > 0 && ncost(i) + phi(nto(i)) - phi(nto(i ^ 1)) > 0)
        {
            pushFlow(i, ed, cost);
            mark[ed] = ti = ti + 2, pre = i;
        }
    }
    ncnt -= 2;
    return ncap(ncnt + 2);
}

// Main

int main(void)
{
    I n, m;
    scanf("%d%d", &n, &m);
    for (I i = 1; i <= n; i++)
    {
        addEdge(2 * n + 1, i, 1, 0);
        addEdge(i + n, 2 * n + 2, 1, 0);
    }
    for (I i = 1; i <= m; i++)
    {
        I u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, n + v, 1, w);
    }
    L cost;
    L flow = simplex(2 * n + 1, 2 * n + 2, &cost);
    printf("%lld\n", cost - 1ll * flow * 0x3f3f3f3f3f3f);
    for (I i = n + 1; i <= n + n; i++)
    {
        for (I j = head[i]; j; j = nnxt(j))
        {
            if (ncap(j)) printf("%d ", nto(j));
        }
    }
    return 0;
}