#include <fstream>
#define INF 1000000
#define NMAX 1001
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct arc{int vf, c;};
arc g[NMAX][NMAX];

int n, m, x0;
int dmin[NMAX];
int prec[NMAX], poz[NMAX];//poz[i]=-1, daca vf nu e in heap, esrepectiv pozitia pe care este pus nodul in heap, daca nodul e in heap

int M[NMAX], h[NMAX];//m-multimea varfurilor selectate
//in h sunt varfurile organizate ca min-heap
int lgh;

void citire();
void afisare();
void dijkstra();
void inserare(int vf);
int extrage_min();
void upgrade(int fiu);
void ad_arc(int x, int y, int c);

int main()
{
    citire();
    dijkstra();
    afisare();

    fout.close();
    return 0;
}

void citire()
{
    int i, m, x, y, c, cost, j;
    fin>>n>>m;
    x0=1;
    /*for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                c[i][j]=INF;*/
    for(i=0; i<m; i++)
    {
        fin>>x>>y>>cost;
        ad_arc(x, y, c);
    }
    /*for(i=1;i<=n;i++)
    {
        cmin[i]=c[start][i];
        tata[i]=start;
    }
    tata[start]=0; viz[start]=1;*/
}

void ad_arc(int x, int y, int c)
{
    g[x][0].c++;
    g[x][g[x][0].c].vf=y;
    g[y][g[y][0].c].vf=x;
}

void dijkstra()
{
    int vfmin, i, j, nrs=0;
    //initializare
    for(i=1;i<=n;i++)
    {
        dmin[i]=INF;
        prec[i]=x0;
        poz[i]=-1;
    }

    dmin[x0]=0;
    prec[x0]=-1;
    poz[x0]=1;
    h[1]=x0;
    lgh=1;

    while(nrs<n)
    {
        if(lgh==0) break;
        else
        {
            vfmin=extrage_min();
            M[vfmin]=1;
            nrs++;
            for(j=1; j<=g[vfmin][0].c; j++)
                if(!M[g[vfmin][j].vf])
                    if(dmin[g[vfmin][j].vf]>dmin[vfmin]+g[vfmin][j].c)
                    {
                       dmin[g[vfmin][j].vf]=dmin[vfmin]+g[vfmin][j].c;
                       prec[g[vfmin][j].vf]=vfmin;
                       if(poz[g[vfmin][j].vf]==-1)
                            inserare(g[vfmin][j].vf);
                        else
                            upgrade(poz[g[vfmin][j].vf]);
                    }
        }
    }
}

void afisare()
{
    int i;
    for(i=2; i<=n; i++)
    {
        fout<<dmin[i]<<' ';

        //fout<<i<<'\n';
    }
}

void inserare(int vf)
{
    h[++lgh]=vf;
    poz[vf]=lgh;
    upgrade(lgh);
}

int extrage_min()
{
    /*int x=h[1];
    h[1]=h[n];
    n--;
    comb_heap(1, n);
    return x;*/

    int fiu, tata, aux;
    int minim=h[1];
    h[1]=h[lgh--];
    poz[h[1]]=-1;

    //downgrade
    tata=1;
    fiu=2*tata;
    while(fiu<=lgh)
    {
        if(fiu<lgh && dmin[h[fiu]]>dmin[h[fiu+1]]) fiu++;
        if(dmin[h[tata]]>dmin[h[fiu]])
        {
            poz[h[fiu]]=tata;
            poz[h[tata]]=fiu;
            aux=h[fiu];
            h[fiu]=h[tata];
            h[tata]=aux;
            tata=fiu;
            fiu=tata*2;
        }
        else break;
    }

    return minim;
}

void upgrade(int fiu)
{
    int tata=fiu/2, aux;
    while(tata && dmin[tata]>dmin[fiu])
    {
        poz[h[fiu]]=tata;
        poz[h[tata]]=fiu;
        aux=h[fiu];
        h[fiu]=h[tata];
        h[tata]=aux;
        fiu=tata;
        tata=fiu/2;
    }
}