#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int N = 50005;
const int INF = 1000000000;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct pereche
{
	int nod,cost;
};

vector<pereche> a[N];
queue<int> q;
bool inq[N];
int nrq[N],d[N],n,m;

void citire()
{
	int x,y,c;
	in>>n>>m;
	while(m--)
	{
		in>>x>>y>>c;
		a[x].push_back((pereche){y,c});
	}
}

void init()
{
	for(int i=1 ; i<=n ; i++)
		d[i] = INF;
}

void scrie()
{
	for(int i=2 ; i<=n ; i++)
		out<<d[i]<<" ";
	out<<"\n";
}

void bf()
{
	int x,y,c;
	init();
	d[1] = 0;
	q.push(1);
	inq[1] = true;
	nrq[1]++;
	while(!q.empty())
	{
		x = q.front();
		q.pop();
		inq[x] = false;
		for(size_t i=0 ; i<a[x].size() ; i++)
		{
			y = a[x][i].nod;
			c = a[x][i].cost;
			if(d[x] + c < d[y])
			{
				d[y] = d[x] + c;
				if(!inq[y])
				{
					q.push(y);
					inq[y] = true;
					nrq[y]++;
					if(nrq[y] == n)
					{
						out<<"Ciclu negativ!\n";
						return;
					}
				}
			}
		}
	}
	scrie();
}

int main()
{
	citire();
	bf();
	return 0;
}