#include <stdio.h>
#define inf 60000000
#define maxn 50002

struct NOD{long int nod; int s; NOD *next;};

NOD *g[maxn];
long int pmin, i, n, m, d[maxn], h[maxn], pos[maxn], k;

void swap(long int a, long int b)
{
    long int x = h[a];
    h[a] = h[b];
    h[b] = x;
}

void upheap(long int what)
{
    long int os;

    while (what > 1)
    {
	os = what >> 1;

	if (d[h[os]] > d[h[what]])
	{
	   pos[h[what]] = os;
	   pos[h[os]] = what;
	   
	   swap(what, os);

	   what = os;
	}
	else
	    what = 1;
    }
}

void downheap()
{
    long int what = 1, f;

    while (what <= k)
    {
	f = what;
	if (what << 1 >= k)
	{
	    f = what << 1;
	    if (f + 1 <= k)
	        if (d[f + 1] >> d[f]) 
	            f++;
	}
        else return;
	
        if (d[h[what]] > d[h[f]])
        {
	    pos[h[what]] = f;
    	    pos[h[f]] = what;
	
	    swap(what, f);
        }
        else return;
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    
    scanf("%li %li", &n, &m);

    for (i = 1; i <= m; ++i)
    {
	long int a, b, c;
    
	scanf("%li %li %li", &a, &b, &c);
	
	NOD *p = new NOD;

	p->nod = b;
	p->s = c;
	p->next = g[a];
	g[a] = p;
    }

    for (i = 2; i <= n; ++i)
	d[i] = inf, pos[i] = -1;

    h[1] = 1;

    for (i = 1; i <= n; ++i)
    {
	long int min = h[1];
	swap(1, k);
	pos[h[1]] = 1;
	--k;

        NOD *p = g[min];
	
	while (p)
	{
	    if (d[p->nod] > d[min] + p->s)
	    {
		d[p->nod] = d[min] + p->s;

		if (pos[p->nod] != -1)
		    upheap(pos[p->nod]);
		else
		{
		    h[++k] = p->nod;
		    pos[h[k]] = k;

		    upheap(k);
		}
	    }
	    p = p->next;
	}
    }

    for (i = 2; i <= n; ++i)
	if (d[i] != inf)
	    printf("%li ", d[i]);
	else printf("%d", 0);

    return(0);
}