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

using namespace std;
typedef unsigned int uint;

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

class Graph
{
	struct cost
	{
		uint node;
		int weight;
	};
	uint V;
	vector<vector<cost>> adj;
public:
	Graph(const uint V);
	void Add_edge(uint x, uint y, int c);
	void Bellmanford(uint start);
};

Graph::Graph(const uint V)
{
	this->V = V;
	adj.assign(V + 1, vector<cost>());
}

void Graph::Add_edge(uint src, uint dest, int weight)
{
	adj[src].push_back({dest,weight});
}

void Graph::Bellmanford(uint start)
{
	const int oo = (1 << 31) - 1;

	vector<int> dist(V + 1, oo);
	dist[start] = 0;

	vector<bool> inQueue(V + 1, false);
	inQueue[start] = true;

	vector<uint> cnt(V + 1, 0);

	queue<uint> Q;
	Q.push(start);

	while (!Q.empty())
	{
		uint src = Q.front();
		Q.pop();
		inQueue[src] = false;

		for (auto &j : adj[src])
		{
			int sum = dist[src] + j.weight;
			if (sum < dist[j.node])
			{
				dist[j.node] = sum;
				if (!inQueue[j.node])
				{
				    ++cnt[j.node];
				    if (cnt[j.node] >= V)
                    {
                        fout << "Ciclu negativ!";
                        exit(0);
                    }

					Q.push(j.node);
					inQueue[j.node] = true;
				}
			}
		}
	}

	for (size_t i = 2; i <= V; ++i)
		fout << dist[i] << ' ';
}

int main()
{
	uint n,m;
	fin >> n >> m;

	Graph G(n);

	for (size_t x,y,c,i = 0; i < m; ++i)
	{
		fin >> x >> y >> c;
		G.Add_edge(x,y,c);
	}

	G.Bellmanford(1);
}