#include<stdio.h>
#include<string.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);

        if (dst[n] == INF)
            return ;
            
        // 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, 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++)
    {
        fgets(linie, sizeof(linie), stdin);
        l = strlen(linie);
        for (j=0,sp=0,a=b=c=0;j<l;j++)
            if (linie[j]>='0' && linie[j]<='9')
            {
                if (sp==0)
                    a=a*10+(linie[j]-'0');
                else if (sp==1)
                    b=b*10+(linie[j]-'0');
                else
                    c=c*10+(linie[j]-'0');
            }
            else if (linie[j]==' ')
                sp++;
        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;
}