#include<iostream>
#include<cstring>
#define INF 1e12
#define maxn 501
using namespace std;

long long g[maxn][maxn],slack[maxn],la[maxn],lb[maxn];
int n,m,match[maxn],vis[maxn],pre[maxn]; 

void bfs(int id){
	memset(vis,0,sizeof(vis));
	memset(slack,0x3f,sizeof(slack));
	int y=0,x=match[0]=id;
	while (1){
		vis[y]=1;
		long long delta=INF; // 一会要更新的  
		int _y=0;
		for (int i=1;i<=n;i++){
			if (vis[i]) continue;
			long long D=la[x]+lb[i]-g[x][i];
			// D: 更新 slack 所用的临时变量 
			if (D<slack[i]){
				// 找到了更小的变化值 
				slack[i]=D,pre[i]=y;
			}
			if (slack[i]<delta){
				delta=slack[i],_y=i;
			}
		}
		la[x]-=delta;
		/*
		因为 x 并没有匹配成功，所以接下来用 match 更新时无法更新到 x 
		*/
		for (int i=1;i<=n;i++){
			if (vis[i]){
				lb[i]+=delta,la[match[i]]-=delta;
			} 
			else slack[i]-=delta;
		}
		if (!match[y=_y]) break;
		x=match[y];
	}
	while (y){
		match[y]=match[pre[y]];
		y=pre[y];
	}
}

int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		la[i]=-INF;
		for (int j=1;j<=n;j++){
			g[i][j]=-INF;
		}
	}
	int u,v,w;
	for (int i=1;i<=m;i++){
		cin>>u>>v>>w;
		g[u][v]=w;
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			la[i]=max(la[i],g[i][j]);
		}
	}
	for (int i=1;i<=n;i++) bfs(i);
	long long ans=0;
	for (int i=1;i<=n;i++){
		ans=ans+la[i]+lb[i];
	}
	cout<<ans<<'\n';
	for (int i=1;i<=n;i++){
		cout<<match[i]<<' ';
	}
	return 0;
} 

记录 谢谢各位大佬