#include <cstdio>
using namespace std;

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

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

int m, n;
int mincost[maxn], queue[maxm], beg=1, end;
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 = new nod;
	p->dest = b;
	p->cost = c;
	p->urm = graf[a];
	graf[a] = p;
}


void citire()
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d%d", &n, &m);
	
	int i; mincost[1] = 0;
	for (i=2; i<=n; ++i)
		mincost[i] = inf;
	
	int a, b, c;
	for (i=1; i<=m; ++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
}

void Dijkstra()
{
	queue[++end] = 1;
	while (end >= beg)
	{
		nod *p = graf[queue[beg]];
		if (viz[queue[beg]])
			p = NULL;
		else viz[queue[beg]] = 1;
		
		while (p)
		{
			queue[++end] = p->dest;
			if (mincost[queue[beg]] + p->cost < mincost[p->dest])
				mincost[p->dest] = mincost[queue[beg]] + p->cost;
			p = p->urm;
		}
		
		++beg;
	}
}

void afisare()
{
	freopen("dijkstra.out", "w", stdout);
	for (int i=2; i<=n; ++i)
		printf("%d ", (mincost[i]==inf ? 0 : mincost[i]));
}

int main()
{
	citire();
	Dijkstra();
	afisare();
	return 0;
}