#include <stdio.h>
#include <stdlib.h>
#define NMAX 50005
#define INF (1<<30)

struct graf {
    int cost, node;
    struct graf *next;
};

struct graf *A[NMAX];
int dist[NMAX], poz[NMAX], h[NMAX];
int N, M, size;

void swap(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void heapUp(int what)
{
    int f;
    while (what > 1) {
        f = what >> 1;
        if (dist[h[f]] > dist[h[what]]) {
	poz[h[f]] = what;
	poz[h[what]] = f;
	swap(f, what);
	what = f;
        }
        else
	what = 1;
    }
}

void heapDown(int what)
{
    int f;
    while (what <= size) {
        f = what;
        if ((what << 1) <= size) {
	f = what << 1;
	if (f+1 <= size) 
	    if (dist[h[f+1]] < dist[h[f]])
	        ++f;
        }
        else 
	return;
        if (dist[h[what]] > dist[h[f]]) {
	poz[h[what]] = f;
	poz[h[f]] = what;
	swap(what, f);
	what = f;
        }
        else
	return;
    }
}

void add(int where, int what, int cost)
{
    struct graf *q = malloc(sizeof(struct graf));
    q->node = what;
    q->cost = cost;
    q->next = A[where];
    A[where] = q;
}   

void read()
{
    int x, y, cost, i;
    scanf("%d %d", &N, &M);
    for (i=1; i<=N; ++i) {
        dist[i] = INF;
        poz[i] = -1;
    }
    
    for (i=1; i<=M; ++i) {
        scanf("%d %d %d", &x, &y, &cost);
        add(x, y, cost);
    }
}

void Dijsktra()
{
    dist[1] = 0;
    h[++size] = 1;
    
    while (size) {
        int min = h[1];
        swap(1, size);
        --size;
        poz[h[1]] = 1;
        
        heapDown(1);
        struct graf *q = A[min];
        while (q) {
	if (dist[q->node] > dist[min] + q->cost) {
	    dist[q->node] = dist[min] + q->cost;
	    if (poz[q->node] != -1)
	        heapUp(poz[q->node]);
	    else {
	        h[++size] = q->node;
	        poz[h[size]] = size;
	        heapUp(size);
	    }
	}
	q = q->next;
        }
    }
}

int main()
{
    int i;
    freopen("dijsktra.in", "r", stdin);
    freopen("dijsktra.out", "w", stdout);
    read();
    Dijsktra();
    for (i=2; i<=N; ++i)
        printf("%d ", (dist[i]==INF)?0:dist[i]);
    return 0;
}