#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

struct node_pair
{
	int a;
	int b;
};

struct edge
{
	int node;
	vector<node_pair> adj;
};

int main(void)
{
	ifstream inp("bellmanford.in");
	ofstream out("bellmanford.out");

	int n, m;

	inp >> n >> m;

	struct edge *nodes = new struct edge[n + 1];
	for(int i = 0; i < m; i++)
	{
		int x, y, c;
		inp >> x >> y >> c;

		struct node_pair np = {y, c};

		nodes[x].adj.push_back(np);
	}

	int *d = new int[n + 1];
	int start = 1;
	const int inf = 2317896;

	memset(d, inf, sizeof(int) * (n + 1));
	d[start] = 0;
	for(int i = 0, len = nodes[start].adj.size(); i < len; i++)
		d[nodes[start].adj[i].a] = nodes[start].adj[i].b;


	// aplicam bellman ford simplu
	bool end = false;
	while(!end)
	{
		end = true;
		for(int i = 1; i <= n; i++)
		{
			for(int j = 0, len = nodes[i].adj.size(); j < len; j++)
			{
				int cost = nodes[i].adj[j].b;
				if(d[i] + cost < d[nodes[i].adj[j].a])
				{
					d[nodes[i].adj[j].a] = d[i] + cost;
					end = false;
				}
			}
		}
	}

	for(int i = 2; i <= n; i++)
		out << d[i] << " ";

	delete[] d;
	delete[] nodes;
	inp.close();
	out.close();

	system("pause");
	return 0;
}