#include <cstdio>
#include<vector>
using namespace std;

struct muchie{int vf;
                int cost;
};

int x0=1,dmin[50005],prec[50005],poz[50005],lgh,n,m;
const int INF=1<<30;
vector <muchie> G[50005];

int h[50005];

void citire(){

    int x,y,c;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;++i){

        scanf("%d%d%d",&x,&y,&c);
        muchie arc;
        arc.vf=y;
        arc.cost=c;
        G[x].push_back(arc);

    }
}

void afisare(){

    for(int i=2;i<=n;++i){
        if(dmin[i]==INF){

            printf("0 ");

        }
        else{
        printf("%d ",dmin[i]);
        }
    }

}
int extractmin(){
    int tata,fiu,aux;
    int minim=h[1];

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

    while(tata<=lgh){

        if(tata<<1<=lgh){ fiu=tata<<1;
            if(dmin[h[fiu]]>dmin[h[fiu+1]] && fiu+1<=lgh)

            ++fiu;
        }
        else break;
        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;

        }
        else break;

    }

    return minim;

}

void upgrade(int fiu){

    int tata,aux;

    while(fiu>1){
        tata=fiu/2;
     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;
        fiu=tata;

    }
    else fiu=1;
    }
}

void insert(int vf){

    h[++lgh]=vf;
    poz[h[lgh]]=lgh;
    upgrade(lgh);

}
void dijkstra(){
    int vfmin;
    for(int i=0;i<=n;++i){

        dmin[i]=INF;
        poz[i]=-1;
    }

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

    while(lgh){

        vfmin=extractmin();

        for(int j=0;j<G[vfmin].size();++j){

                if(dmin[G[vfmin][j].vf]>dmin[vfmin]+G[vfmin][j].cost){

                    dmin[G[vfmin][j].vf]=dmin[vfmin]+G[vfmin][j].cost;

                    if(poz[G[vfmin][j].vf]==-1){

                        insert(G[vfmin][j].vf);
                    }
                    else{

                        upgrade(poz[G[vfmin][j].vf]);

                    }

                }

        }

    }

}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();
    dijkstra();
    afisare();

    return 0;
}