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

using namespace std;

typedef struct { int x, dist; } nod;
int N, M, poz[NMax], el, dst[NMax];
nod heap[NMax];
vector<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);

        // luam toti vecinii lui n si ii actualizam
        nr=v[n].size();
        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, a, b, c;
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(b);
        d[a].push_back(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;
}