#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define node first
#define cost second

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

const int INF = 0x3f3f3f3f;
int N, M, D[50005];
int Ap[50005];
bool InQ[50005];
vector <pair<int,int> > G[50005];
queue <int> Q;

void Read();
bool BellmanFord();
void Write();

int main()
{
	Read();
	if (BellmanFord() == 1)
		os << "Ciclu negativ!";
	else
		Write();
	is.close();
	os.close();
};

void Read()
{
	is >> N >> M;
	for (int i = 1, a, b, c; i <= M; ++i)
	{
		is >> a >> b >> c;
		G[a].push_back({b, c});
	}
	for (int i = 1; i <= N; ++i)
		D[i] = INF;
};

bool BellmanFord()
{
	Q.push(1);
	D[1] = 0;
	InQ[1] = 1;
	Ap[1] = 1;
	for (int x; !Q.empty();)
	{
		x = Q.front();
		InQ[x] = 0; Q.pop();
		for (const auto& y : G[x])
			if (D[y.node] > D[x] + y.cost)
			{
				D[y.node] = D[x] + y.cost;
				if (InQ[y.node] == 0)
				{
					Ap[y.node]++;
					if (Ap[y.node] == N)
						return 1;
					Q.push(y.node);
					InQ[y.node] = 1;
				}
			}
	}
	return 0;
};

void Write()
{
	for (int i = 2; i <= N; ++i)
		os << D[i] << ' ';
};