#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], ok[maxn];

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;

    for (i = 1; i <= n; ++i)
    {
	int min = inf;

	for (int j = 1; j <= n; ++j)
	    if (d[j] < min && !ok[j]) min = d[j], pmin = j;

	ok[pmin] = 1;

	NOD *p = g[pmin];

	while (p)
	{
	    if (d[p->nod] > d[pmin] + p->s)
		d[p->nod] = d[pmin] + p->s;
	    p = p->next;
	}
    }

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

    fclose(stdin);
    fclose(stdout);
}