#时间复杂度为Θ(n^3)

const int inf =0x3f3f3f3f;
const int N=505;
long long w[N][N];
long long la[N],lb[N];
bool va[N],vb[N];
long long match[N];
long long n,m,upd[N];
long long last[N];

bool dfs(int x,int fa)
{
    va[x]=1;
    for(int y = 1; y<=n; y++)
    {
        if(!vb[y])
        {
            if(la[x]+lb[y]-w[x][y]==0)
            {
                vb[y]=1;
                last[y]=fa;
                if(!match[y]||dfs(match[y],y))
                {
                    match[y]=x;
                    return true;
                }
            }
            else if(upd[y]>la[x]+lb[y]-w[x][y])
            {
                upd[y]=la[x]+lb[y]-w[x][y];
                last[y]=fa;
            }
        }
    }
    return false;
}

long long KM()
{
    memset(match,0,sizeof match);
    memset(lb,0,sizeof lb);
    for(int i = 1; i<=n; i++)
    {
        la[i]=w[i][1];
        for(int j = 2; j<=n; j++) la[i]=max(la[i],w[i][j]);
    }
    for(int i = 1; i<=n; i++)
    {
        memset(upd,0x7f,sizeof upd);
        memset(va,0,sizeof va);
        memset(vb,0,sizeof vb);
        memset(last,0,sizeof last);
        int st=0;
        match[0]=i;
        while(match[st])
        {
            if(dfs(match[st],st)) break;
            long long delta=(0x7fffffff);
            for(int j = 1; j<=n; j++) if(!vb[j] && upd[j]<delta) delta=upd[j],st=j;
            for(int j =1; j<=n; j++)
            {
                if(va[j]) la[j]-=delta;
                if(vb[j]) lb[j]+=delta;
                else upd[j]-=delta;
            }
            vb[st]=1;
        }
        while(st)
        {
            match[st]=match[last[st]];
            st=last[st];
        }
    }
    long long ans=0;
    for(int i = 1; i<=n; i++) ans+=w[match[i]][i];
    return ans;
}

int main()
{
    memset(w,-inf,sizeof w);
    cin>>n>>m;
    long long u,v,c;
    while(m--)
    {
        cin>>u>>v>>c;
        w[u][v]=c;
    }
    cout<<KM()<<'\n';
    for(int i =1 ; i<=n; i++)
    {
        cout<<match[i]<<' ';
    }
    return 0;
}