#include<cstdio>
#include<algorithm>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define n_max 50005
#define INF 1 << 30
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
using namespace std;

int n,m;

typedef struct nod {
	int inf, cost;
	nod * urm;
} *pnod;

pnod v[n_max];

int h[n_max], d[n_max], poz[n_max];
int N;


void citeste();
void add(pnod&, int, int);
void sift(int);
void percolate(int);
void rezolva();
void afiseaza();


void init()
{
	h[++N] = 1;
	poz[1] = 1;
	
	for(int i=2;i<=n;i++)
		d[i] = INF;
}



void add( pnod &p, int x, int c)
{
	pnod q = new nod;
	
	q->inf = x;
	q->cost = c;
	q->urm = p;
	
	p=q;
}



void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&n,&m);
	
	int x,y,c;
	
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&c);
		
		add(v[x],y,c);
	}
	
	fclose(stdin);
}


int get_min_heap()
{
	int minim = h[1];
	
	h[1] = h[N--];
	
	poz[ h[1] ] = 1;
	
	sift(1);
	
	return minim;
}


void sift(int k)
{
	int son = k, l = ls(k), r =rs(k);
	
	if(l<=N && d[h[son]] > d[h[l]])
		son = l;
	if(r<=N && d[h[son]] > d[h[r]])
		son = r;
	if(son!=k)
	{
		swap(poz[h[son]], poz[h[k]]);
		swap(h[son], h[k]);
		sift(son);
	}
}




void percolate(int k)
{
	while(k>1 && d[h[f(k)]] > d[h[k]])
	{
		swap(poz[h[k]], poz[h[f(k)]]);
		swap(h[k], h[f(k)]);
		
		k = f(k);
	}
}




void rezolva()
{
	int nodm;
	
	while(N)
	{
		nodm = get_min_heap();
		
		pnod q = v[nodm];
		
		while(q)
		{
			if(d[q->inf] > d[nodm] + q->cost)
			{
				d[q->inf] = d[nodm] + q->cost;
				
				if(poz[q->inf])
					percolate(poz[q->inf]);
				else
				{
					h[++N] = q->inf;
					poz[q->inf] = N;
					percolate(poz[q->inf]);
				}
			}			
			q = q->urm;
		}
	}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	for(int i=2;i<=n;i++)
		printf("%d ",d[i] == INF ? 0 : d[i]);

	fclose(stdout);
}




int main()
{
	citeste();
	init();
	rezolva();
	afiseaza();
	
	return 0;
}