#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 100000000
#define NMax 50005

typedef struct { int x, dist; } nod;
int N, M, poz[NMax], el, dst[NMax], grad[NMax];
nod heap[NMax];
int *v[NMax], *d[NMax];

void percolate(int n)
{
    nod aux;
    for(;n>1;n/=2)
        if(heap[n].dist < heap[n/2].dist)
        {
            aux=heap[n];
            heap[n]=heap[n/2];
            heap[n/2]=aux;

            poz[heap[n].x] = n;
            poz[heap[n/2].x] = n/2;
        }
        else
            return;
}

void sift(int n)
{
    for (;n*2<=N;)
    {
        int imin=2*n;
        if(n*2+1<=N && heap[2*n+1].dist<heap[2*n].dist)
            imin=2*n+1;

        if (heap[n].dist<=heap[imin].dist)
            return ;

        nod aux=heap[n];
        heap[n]=heap[imin];
        heap[imin]=aux;

        poz[heap[n].x] = n;
        poz[heap[imin].x] = imin;
        
        n=imin;
    }
}

void dijkstra()
{
    int i, j, n, nr, p;

    for (i = 1; i <= N-1; i++)
    {
        n = heap[1].x;

        // stergem minimul (radacina heapului)
        heap[1] = heap[el--];
        poz[heap[1].x] = 1;
        sift(1);

        if (dst[n] == INF)
            return ;
            
        // luam toti vecinii lui n si ii actualizam
        nr=grad[n];
        for (j = 0; j < nr; j++)
        {
            p = v[n][j];
            if (dst[n] + d[n][j] < dst[p])
            {
                dst[p] = dst[n] + d[n][j];
                heap[poz[p]].dist = dst[p];
                percolate(poz[p]);
            }
        }
    }
    
}

int main ()
{
    int i, j, l, a, b, c, sp;
    char linie[32];
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d\n",&N,&M);

    for(i=1;i<=M;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        grad[a]++;
        v[a]=(int*)realloc(v[a], sizeof(int) * grad[a]);
        d[a]=(int*)realloc(d[a], sizeof(int) * grad[a]);

        v[a][grad[a]-1] = b;
        d[a][grad[a]-1] = c;
    }
    for(i=1;i<=N;i++)
    {
        heap[i].x=i;
        heap[i].dist=INF;
        poz[i]=i;
        dst[i] = INF;
    }
    el = N;
    heap[1].dist=0;
    dst[1] = 0;
    dijkstra();

    for (i = 2; i <= N; i++)
        if (dst[i] != INF)
            printf("%d ", dst[i]);
        else
            printf("0 ");
    printf("\n");

    return 0;
}