#include<cstdio>
#include<cstring>
#include<iostream>
#define inc(i,x,y) for(register LL i=x;i<=y;i++)
using namespace std;
typedef long long LL;
const LL N=505,Max=1e18;
LL n,m,tx[N],ty[N],match[N],slack[N],E[N][N];
bool vx[N],vy[N];
inline LL Rd(){
	LL s=0;int w=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*w;
}
inline bool dfs(LL x){
	vy[x]=1;
	inc(i,1,n){
		if(!vx[i]){
			LL dis=tx[i]+ty[x]-E[x][i];
			if(dis) slack[i]=min(slack[i],dis);
			else{
				vx[i]=1;
				if(!match[i]||dfs(match[i])){
					match[i]=x;
					return 1;
				}
			}
		}
	}
	return 0;
}
inline LL km(){
	inc(i,1,n){
		ty[i]=E[i][1];
		inc(j,2,n) ty[i]=max(ty[i],E[i][j]);
	}
	inc(i,1,n){
		inc(j,1,n) slack[j]=Max;
		while (1){
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			if(dfs(i)) break;
			LL d=Max;
			inc(j,1,n) if(!vx[j]) d=min(d,slack[j]);
			inc(j,1,n){
				if(vy[j]) ty[j]-=d;
				if(vx[j]) tx[j]+=d;
				else slack[i]-=d;
			}
		}
	}
	LL tot=0;
	inc(i,1,n) tot+=E[match[i]][i];
	return tot;
}
int main(){
	n=Rd();m=Rd();
	inc(i,1,n) inc(j,1,m) E[i][j]=-Max;
	inc(i,1,m) E[Rd()][Rd()]=Rd();
	printf("%lld\n",km());
	inc(i,1,n) printf("%lld ",match[i]);
	return 0;
}