#include <fstream>
#define Infinit 1000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Arc{int vf; int c;};

int n,m,x0,start;
Arc G[10000][10001];
int poz[10001]; //poz[i]=-1 daca vf i nu a fost pus in heap, respectiv 1 daca a fost pus in heap
int dmin[10001]; //distantele minime
int prec[10001]; //pot reconstitui drumul
int h[10001],lgh; //in h sunt varfurile organizate ca min-heap
int M[10001]; //multimea varfurilor selectate

void citire();
int extrage();
void adauga_arc(int x, int y, int cost);
void dijkstra();
void InsertHeap(int vf);
void upGrade(int fiu);
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i,x,y,cost;
    fin>>n>>m;
    x0=1;
    for(i=0;i<m;i++)
        {
            fin>>x>>y>>cost;
            adauga_arc(x,y,cost);
        }
}

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

void dijkstra()
{
    int i,vfmin,nrs=1,j;
    //initializari
    for(i=1;i<=n;i++) {dmin[i]=Infinit; prec[i]=x0; poz[i]=-1;}
    //x0 intra in heap pe poz 1
    dmin[x0]=0; prec[x0]=-1; poz[x0]=1; h[1]=x0; lgh=1;

    while(nrs<n)
    {
        vfmin=extrage();
        M[vfmin]=1; nrs++;
        //parcurg lista de adiacenta a lui vfmin
        for(j=1;j<=G[vfmin][0].c;j++)
                if(!M[G[vfmin][j].vf]) //nu a fost deja selectat
                    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)
                        InsertHeap(G[vfmin][j].vf);
                    else
                        upGrade(poz[G[vfmin][j].vf]);

                }
    }
}

void InsertHeap(int vf)
{
    h[++lgh]=vf; poz[vf]=lgh;
    upGrade(lgh);
}

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;
    }
}

void afisare()
{
    int i;
    for(i=1;i<=n;i++)
        if(i!=x0)
            fout<<dmin[i]<<' ';
}

int extrage()
{
    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=2*tata;
        }
        else break;
     }
    return minim;
}