#include <fstream>
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();
}

void Dijkstra(int start)
{
	nod *p = graf[start];
	while (p)
	{
		if (p->cost + mincost[start] < mincost[p->dest])
			mincost[p->dest] = p->cost + mincost[start];
		p = p->urm;
	}
	viz[start] = 1;
	p = graf[start];
	while (p)
	{
		if (!viz[p->dest])
			Dijkstra(p->dest);
		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();
	Dijkstra(1);
	afisare();
	return 0;
}