#include<fstream>
#include<vector>
#include<queue>
#define mn INT_MIN
using namespace std;
vector<int> v[30005],c[30005];
queue<int> q;
int d[30005];
bool viz[30005];
int m,n;
void citire()
{
	int i,x,y,e;
	ifstream in("bellmanford.in");
	in>>n>>m;
	for (i=1;i<=m;i++)
	{
		in>>x>>y>>e;
		v[x].push_back(y);
		c[x].push_back(e);
	}
	//for (i=1;i<=n;i++)
	//	d[i]=mn;
}
void af(int a)
{
	ofstream out("bellmanford.out");
	out<<"Ciclu negativ!  "<<a;
	out.close();
	exit(0);
}
void afisare()
{
	int i;
	ofstream out("bellmanford.out");
	for (i=2;i<=n;i++)
		out<<d[i]<<" ";
	out<<'\n';
}
	
int main()
{
	int i,x,y;	
	citire();
	q.push(1);
	d[1]=0;
	viz[1]=1;
	while (!q.empty())
	{
		x=q.front();
		q.pop();
		
		for (i=0;i<(int)v[x].size();i++)
		{
			y=v[x][i];
			if (!viz[y])
			{
				//if (d[y]>d[x]+c[x][i])
				{
					d[y]=d[x]+c[x][i];
					q.push(y);
					viz[y]=1;
				}				
			}
			else if (d[x]+c[x][i]<d[y])
			{
				d[y]=d[x]+c[x][i];
				q.push(y);
				if (d[y]<0)
					af(y);
			}
			
		}
	}
	afisare();
}