#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
int cnt,i,j,k,m,n,pth[maxn+10];
bool by[maxn+10],bz[maxn+10];
long long mn,p[maxn+10][maxn+10],sumn,u,v,w,x[maxn+10],y[maxn+10];
bool findpth(int xx)
{
	int i;
	by[xx]=true;
	for(i=n;i>=1;--i)
	{
		if(!bz[i]&&x[xx]+y[i]==p[xx][i])
		{
			bz[i]=true;
			if(!pth[i]||findpth(pth[i]))
			{
				pth[i]=xx;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	//freopen("P6577_2.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			p[i][j]=LLONG_MIN;
	while(m--)
	{
		scanf("%d%d%lld",&u,&v,&w);
		p[u][v]=w;
	}
	for(i=1;i<=n;++i)
	{
		x[i]=LLONG_MIN;
		for(j=1;j<=n;++j)
			x[i]=max(x[i],p[i][j]);
	}
	for(i=1;i<=n;++i)
	{
		while(!findpth(i))
		{
			mn=LLONG_MAX;
			for(j=1;j<=n;++j)
				if(by[j])
					for(k=1;k<=n;++k)
						if(!bz[k])
							mn=min(mn,x[j]+y[k]-p[j][k]);
			for(j=1;j<=n;++j)
			{
				if(by[j])
					x[j]-=mn;
				if(bz[j])
					y[j]+=mn;
			}
			memset(by,false,sizeof by);
			memset(bz,false,sizeof bz);
		}
	}
	for(i=1;i<=n;++i)
		sumn+=p[pth[i]][i];
	printf("%lld\n",sumn);
	for(i=1;i<=n;++i)
		printf("%d ",pth[i]);
	return 0;
}

记录，不明白为啥会有 WA，求调，悬赏 $3$ 个关注。