#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#define NMAX 50005
#define INFINIT 1000000

using namespace std;

FILE * fin = fopen("bellmanford.in", "r");
FILE * fout = fopen("bellmanford.out", "w");

void citire();
bool bellmanford();
void afisare();

int n, m;
queue <int> coada;
vector < pair<int, int> > graf[NMAX];
int dmin[NMAX], nr[NMAX], pred[NMAX];
int main()
{
	citire();
	if (bellmanford() == true)
		afisare();
	else
		fprintf(fout, "Ciclu negativ!\n");
	return 0;
}

void citire()
{
	int i, x, y, cost;
	fscanf(fin, "%d %d", &n, &m);
	for (i = 1; i <= m; i ++)
	{
		fscanf(fin, "%d%d%d", &x, &y, &cost);
		graf[x].push_back(make_pair(y, cost));
	}
}

bool bellmanford()
{
	int i, x, y, c;
	for (i = 2; i <= n; i ++)
	{
		pred[i] = 1;
		dmin[i] = INFINIT;
	}
	coada.push(1);
	nr[1] ++;
	while (!coada.empty())
	{
		x = coada.front();
		coada.pop();
		for (i = 0; i < graf[x].size(); i ++)
		{
			y = graf[x][i].first;
			c = graf[x][i].second;
			if (dmin[y] > dmin[x] + c)
			{
				dmin[y] = dmin[x] + c;
				pred[y] = x;
				coada.push(y);
				nr[y] ++;
				if (nr[y] == n)
					return false;
			}
		}
	}
	return true;
}

void afisare()
{
	int i;
	for (i = 2; i <= n; i ++)
		fprintf(fout, "%d ", dmin[i]);
	fprintf(fout, "\n");
}