#include<bits/stdc++.h>
using namespace std;
const int NN=105;
struct node{
	int y,w;
};
int n,m,rd[NN],day[NN],pre[NN];
vector<node>e[105]; 
void tuopu()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(rd[i]==0)
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(auto ha:e[x])
		{
			int y=ha.y,w=ha.w;
			if(day[x]+w>day[y])
			{
				pre[y]=x;
				day[y]=day[x]+w;
			}
			rd[y]--;
			if(rd[y]==0)
			{
				q.push(y);
			}
		}
	}
}
void dfs(int oo)
{
	if(pre[oo]!=0) dfs(pre[oo]);
	printf("%d ",oo);
}
int main()
{
	scanf("%d%d",&n,&m);
	n++; 
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back(node{y,z});
		rd[y]++;
	}
	tuopu();
	int anss=0;
	for(int i=1;i<=n;i++) anss=max(anss,day[i]);
	printf("%d\n",anss);
	dfs(n);
}