#include <fstream>
#define NMAX 50000
#define INF 99999999

using namespace std;

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

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

void citire();
void dijkstra();

void Insert_heap(int vf);
void Upgrade(int fiu);
int extract_min();

void afisare();

int cmin[NMAX];
int tata[NMAX],M[NMAX];
int h[NMAX]; //heap-ul
int sol[NMAX];
int n,m,x0;
int poz[NMAX]; //va fi -1 daca varful nu a fost pus in heap
int lgh;

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

    fout.close();
    return 0;
}

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

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

void citire()
{
    int i,j,x,y,z;
    fin>>n>>m; // citim nr de varfuri, de arce si varful de start

    x0=1;M[x0]=1;

    for(i=1;i<=m;i++)
    {
		// citim si punem costurile in matrice
        fin>>x>>y>>z;
        adauga_arc(x,y,z);
    }
}

void dijkstra()
{
   int i,j,nrs=1,vfmin;

    for(i=1;i<=n;i++)
        cmin[i]=INF,tata[i]=x0,poz[i]=-1;

    cmin[x0]=0;
    tata[x0]=-1;
    poz[x0]=1;
    h[1]=x0;
    lgh=1;

    while(nrs<n)
    {
    vfmin=extract_min();
    M[vfmin]=1;// adaugam in multimea varfurilor vizitate deja varful curent
    nrs++;

    for(j=1;j<=g[vfmin][0].c;j++)  //actualizam costurile daca exista o varianta mai buna
        if(!M[g[vfmin][j].vf] && cmin[g[vfmin][j].vf]>cmin[vfmin]+g[vfmin][j].c)
            {
            cmin[g[vfmin][j].vf]=cmin[vfmin]+g[vfmin][j].c;
            tata[g[vfmin][j].vf]=vfmin;
            if(poz[g[vfmin][j].vf]==-1)
                Insert_heap(g[vfmin][j].vf);
                else
                Upgrade(poz[g[vfmin][j].vf]);
            }



   }
}

int extract_min()
{
int fiu,tata,aux;

int minim=h[1];

h[1]=h[lgh--];poz[h[1]]=-1;

while(fiu<=lgh)
        {

        if(fiu<lgh && cmin[h[fiu]]>cmin[h[fiu+1]]) fiu++;

        if(cmin[h[tata]]>cmin[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 Insert_heap(int vf)
{
h[++lgh]=vf;
poz[vf]=lgh;
Upgrade(lgh);
}

void Upgrade(int fiu)
{
int tata=fiu/2, aux;

while(tata && cmin[tata]>cmin[fiu])
    {
    poz[h[fiu]]=tata;
    poz[h[tata]]=fiu;
    aux=h[fiu];h[fiu]=h[tata];h[tata]=aux;
    fiu=tata;
    tata=fiu/2;
    }
}