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

#define inf 1000000000
#define NMax 1000003

using namespace std;

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



/*struct Nod
{
	int nod, cost;
	Nod *next;
};

Nod *t, *Vecin[NMax];
*/
vector<int>graf[NMax];
int j, m, n, x, y, costul, nod, d[NMax];
queue<int>coada;

void adauga(int x, int y, int costul)
{
	Nod *q = new Nod;
	q->nod = y;
	q->cost = costul;
	q->next = Vecin[x];
	Vecin[x] = q;
}

void bellman_ford(){
	int i;
	for (i = 1; i <= n; i++)
		d[i] = inf;
	coada.push(1);
	d[1] = 0;
	while (!coada.empty())
	{
		j = coada.front();
		coada.pop();
		t = Vecin[j];
		while (t)
		{
			if (d[t->nod]>d[j] + t->cost)
			{
				coada.push(t->nod);
				d[t->nod] = d[j] + t->cost;
			}
			t = t->next;
		}
	}
}

int main()
{
	int i;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> costul;
		adauga(x, y, costul);
	}
	bellman_ford();
	for (int i = 2; i <= n; i++)
		if (d[i] == inf)
			g << 0 << " ";
		else
			g << d[i] << " ";
	f.close();
	g.close();
	return 0;
}