#include<queue>
#include<iostream>
#include<cstring>

using namespace std;
const int maxn=550;
const int inf=100000000;

int n,m;
int px[maxn],py[maxn],cx[maxn],cy[maxn],w[maxn][maxn],vx[maxn],vy[maxn],slack[maxn],pre[maxn];
queue<int> q;


template<class type> const void read(type &in)
{
	in=0;
	int f=1;
	char ch=getchar();
	while(ch<48||ch>57)
	{
		ch=getchar();
		if(ch=='-')f=-1;
	}
	while(ch>47&&ch<58)
	{
		in=(in<<1)+(in<<3)+(ch&15);
		ch=getchar();
	}
	in*=f;
	return;
}

void aug(int v)
{
	int t;
	while(v)//增广路扩充路径 
	{
		t=px[pre[v]];
		px[pre[v]]=v;
		py[v]=pre[v];
		v=t;
	}
}

void bfs(int s)
{
	memset(vx,0,sizeof(vx));
	memset(vy,0,sizeof(vy));
	for(int i=1;i<=n;i++)slack[i]=inf;
	while(!q.empty())q.pop();
	q.push(s);
	
	while(1)
	{
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			vx[u]=1;
			for(int i=1;i<=n;i++)
			{
				if(w[u][i]!=-inf)
				{
					if(!vy[i])
					{
						if(cx[u]+cy[i]-w[u][i]<slack[i])
						{
							slack[i]=cx[u]+cy[i]-w[u][i];
							pre[i]=u;
							if(slack[i]==0)
							{
								vy[i]=1;
								if(!py[i]){aug(i);return;}
								else q.push(py[i]);
							}
						}
					}
				}
			}
		}
		int d=inf;
		for(int i=1;i<=n;i++)if(!vy[i])d=min(d,slack[i]);
		for(int i=1;i<=n;i++)
		{
			if(vx[i])cx[i]-=d;
			if(vy[i])cy[i]+=d;
			else slack[i]-=d;
		}
		for(int i=1;i<=n;i++)
		{
			if(!vy[i])
			{
				if(slack[i]==0)
				{
					vy[i]=1;
					if(!py[i]){aug(i);return;}
					else q.push(py[i]);
				}
			}
		}
	}
}

int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=-inf;
	int u,v,val;
	for(int i=1;i<=m;i++)
		read(u),read(v),read(val),w[u][v]=val,cx[u]=max(cx[u],val);
	for(int i=1;i<=n;i++)
		bfs(i);
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=w[i][px[i]];
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++)
		cout<<py[i]<<' ';
}