#include <cstdio>
#include <cstdlib>
#include <list>

using namespace std;

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

struct muchie
{
	int d,c;
	muchie * next;
};

muchie * a[50000];
bool bif[50000];
int hp[50000];
int hpp[50000];
int hpn;
int d[50000];

inline bool hp_cmp(int a, int b)
{
	return d[hp[a]]<d[hp[b]];
}

inline void hp_swp(int a, int b)
{
	hp[a] = hp[a] ^ hp[b];
	hp[b] = hp[a] ^ hp[b];
	hp[a] = hp[a] ^ hp[b];
	hpp[hp[a]]=a;
	hpp[hp[b]]=b;
}

void hp_up(int i)
{
	while (i)
	{
		int t = ((i+1)>>1)-1;
		if (hp_cmp(t, i))
			break;
		hp_swp(i, t);
		i = t;
	}
}

void hp_down(int i)
{
	while (1)
	{
		int min = i;
		int p1 = (i<<1)+1;
		int p2 = (i<<1)+2;
		if ((p1<hpn) && hp_cmp(p1, min))
			min = p1;
		if ((p2<hpn) && hp_cmp(p2, min))
			min = p2;
		if (min == i)
			break;
		hp_swp(i, min);
		i = min;
	}
}

inline int hp_pop()
{
	hpn--;
	hp_swp(0,hpn);
	hp_down(0);
	return hp[hpn];
}

inline int max(int a, int b)
{
	return a>b?a:b;
}

int main (int argc, char * const argv[]) {
	int n,m;
	fscanf(fin, "%d%d",&n,&m);
	for (int i=0; i<n; i++)
	{
		hp[i] = i;
		hpp[i] = i;
		d[i] = 0x3f3f3f3f;
		bif[i] = 0;
		a[i] = NULL;
	}
	d[0] = 0;
	hpn = n;
	for (int i=0; i<m; i++)
	{
		muchie * tmp;
		int x,y,c;
		fscanf(fin, "%d%d%d",&x,&y,&c);
		x--; y--;
		tmp = new muchie;
		tmp->d = y;
		tmp->c = c;
		tmp->next = a[x];
		a[x] = tmp;
	}
	while (hpn)
	{
		int cr = hp_pop();
		bif[cr] = 1;
		for (muchie * i = a[cr]; i!= NULL; i=i->next)
		{
			if (bif[i->d]) continue;
			if (d[cr]+(i->c)<d[i->d])
			{
				d[i->d] = d[cr]+(i->c);
				hp_up(hpp[i->d]);
			}
		}
	}
	for (int i=1; i<n; i++)
	{
		if (d[i]>=0x3f3f3f3f)
			d[i] = 0;
		fprintf(fout, "%d ",d[i]);
	}
	fprintf(fout, "\n");
	fclose(fin);
	fclose(fout);
    return 0;
}