#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

typedef struct graf
{
    int nod;
    int cost;
    struct graf *urm;
}GRAF;

int inf = INT_MAX;
int n; //numar noduri
int m; //numar muchii
int size; //dimensiune heap

int h[50001];
int d[50001];
int poz[50001];

GRAF *g[50001];

void adauga(int a, int b, int c)
{
    GRAF *q=(GRAF*)malloc(sizeof(GRAF));
    q->nod=b;
    q->cost=c;
    q->urm=g[a];
    g[a]=q;
}

void percolate(int k)
{
    int tata,aux;
    tata=k>>1;

    while (tata && d[h[tata]]>d[h[k]])
    {
        poz[h[tata]]=k;
        poz[h[k]]=tata;

        aux=h[tata];
        h[tata]=h[k];
        h[k]=aux;

        k=tata;
        tata=k>>1;
    }
}

void sift(int k)
{
    int fiu,aux;

    h[k]=h[size];
    poz[h[k]]=k;
    size--;

    fiu=0;

    while(k!=fiu)
    {
        fiu=k;
        if (k<<1<=size && d[h[k<<1]]<d[h[k]])
            fiu=k<<1;
        if (k<<1 +1<=size && d[h[k<<1+1]]<d[h[k<<1]])
                fiu=k<<1+1;
        if (k!=fiu)
        {
            poz[h[k]]=fiu;
            poz[h[fiu]]=k;

            aux=h[k];
            h[k]=h[fiu];
            h[fiu]=aux;
        }
    }
}


void dijkstra()
{
    int minim;
    GRAF *q;

    while(size!=0)
    {
        minim=h[1];

        sift(1);

        q=g[minim];

        while (q!=NULL)
        {
            if (d[q->nod]>d[minim]+q->cost)
                {
                    d[q->nod]=d[minim]+q->cost;
                    if (poz[q->nod]==-1)
                    {
                        h[++size]=q->nod;
                        poz[h[size]]=size;
                        percolate(size);
                    }
                    else
                        percolate(poz[q->nod]);
                }
            q=q->urm;
        }
    }
}

int main()
{
    int i;
    FILE *g=fopen("dijkstra.out","w");

    int a,b,c;
    FILE *f=fopen("dijkstra.in","r");

    fscanf(f,"%d%d",&n,&m);

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        adauga(a,b,c);
    }
    fclose(f);

    h[++size]=1;
    poz[1]=1;

    for (i=2;i<=n;i++)
    {
        d[i]=inf;
        poz[i]=-1;
    }

    dijkstra();

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

    fclose(g);
    return 0;
}