#include <fstream>
#include <iostream>
using namespace std;

const int maxn = 50001;
const int inf = 1<<30;

struct nod
{
	int dest, cost;
	nod *urm;
}*graf[maxn];

int m, n, mincost[maxn];
bool viz[maxn];

void add(int a, int b, int c)
{
	if (graf[a] == NULL)
	{
		graf[a] = new nod;
		graf[a]->dest = b;
		graf[a]->cost = c;
		graf[a]->urm = NULL;
		return;
	}
	nod *p = graf[a];
	while (p->urm) p = p->urm;
	p->urm = new nod;
	p->urm->dest = b;
	p->urm->cost = c;
	p->urm->urm = NULL;
}

void citire()
{
	ifstream in("dijkstra.in");
	in>>n>>m;
	int i, a, b, c;
	for (i=2; i<=n; ++i)
		mincost[i] = inf;
	for (i=1; i<=m; ++i)
	{
		in>>a>>b>>c;
		add(a, b, c);
	}
	in.close();
}

int c[maxn], ic=1, sfc;

void BFS(int start)
{
	viz[start] = 1;
	c[++sfc] = start;
	do
	{
		nod *p = graf[c[ic]];
		while (p)
		{
			if (!viz[p->dest])
			{
				c[++sfc] = p->dest;
				viz[p->dest] = 1;
			}
			p = p->urm;
		}
		ic++;
	}
	while (ic < sfc);
}

void Dijkstra(int start)
{
	nod *p = graf[start];
	while (p)
	{
		if (mincost[start] + p->cost < mincost[p->dest])
			mincost[p->dest] = mincost[start] + p->cost;
		p = p->urm;
	}
}

void afisare()
{
	ofstream out("dijkstra.out");
	for (int i=2; i<=n; ++i)
		if (mincost[i] == inf) out<<"0 ";
		else out<<mincost[i]<<" ";
	out.close();
}

int main()
{
	citire();
	BFS(1);
	for (int i=1; i<=n; ++i)
		Dijkstra(i);
	afisare();
	return 0;
}