#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int w[501][501]={-inf},lx[501],ly[501];
int slack[501],matchv[501],pre[501],matchu[501];
bool visv[501],visu[501];
int n,m;
queue<int> q;
bool check(int v){
	visv[v]=1;
	if(matchv[v]){
		if(!visu[matchv[v]]){
			q.push(matchv[v]);
			visu[matchv[v]]=1;
		}
		return false;
	}
	while(v){
		matchv[v]=pre[v];
		int t=matchu[pre[v]];
		matchu[pre[v]]=v;
		v=t;
	}
	return true;
}
void bfs(int uu){
	memset(visv,0,sizeof(visv));
	memset(visu,0,sizeof(visu));
	memset(slack,0x3f,sizeof(slack));
	
	while(!q.empty()){
		q.pop();
	}
	q.push(uu);
	visu[uu]=1;
	while(1){//cout<<"sb";
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int v=1;v<=n;v++){
				if(visv[v]) continue;
				if(lx[u]+ly[v]-w[u][v]<slack[v]){
					slack[v]=lx[u]+ly[v]-w[u][v];
					pre[v]=u;
					if(slack==0 and check(v)) return;
				}
			}
		}
		int d=inf;
		for(int i=1;i<=n;i++){
			if(!visv[i]){
				d=min(d,slack[i]);
			}
		}
		for(int i=1;i<=n;i++){
			if(visu[i]) lx[i]-=d;
			if(visv[i]) ly[i]+=d;
			else slack[i]-=d;
		}
		for(int i=1;i<=n;i++){
			if(visu[i]) continue;
			if(slack[i]==0 and check(i)) return;
		}
	}
}
void km(){
	for(int i=1;i<=n;i++) bfs(i);
}
signed main(){
	cin>>n>>m;
	while(m--){
		int y,c,h;
		cin>>y>>c>>h;
		w[y][c]=h;
	}
	km();
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=w[i][matchu[i]];
	}
	cout<<sum<<endl;
	for(int i=1;i<=n;i++){
		cout<<matchu[i]<<" ";
	}
	return 0;
}