#include <cstdio>
#include<vector>
#define NMAX 50008
#define INF 1000000000
using namespace std;

struct muchie{int vf;int cost;};
vector <muchie> G[NMAX];


int x0=1;
int dmin[NMAX],prec[NMAX],poz[NMAX];
int n,m,lgh;
int h[NMAX];

void dijkstra();
void citire();
void afisare();
int extractmin();
void upgrade(int fiu);
void insert(int vf);

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

    citire();
    dijkstra();
    afisare();
    return 0;
}
void citire()
{
    int i,x,y,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        muchie nou;
        nou.vf=y;
        nou.cost=c;
        G[x].push_back(nou);
    }
}

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 i,j,vfmin;
    for(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(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]);
            }
    }
}

void afisare()
{
    int i;
    for(i=2;i<=n;i++)
    {
        if(dmin[i]==INF)
            printf("0 ");
        else
            printf("%d ",dmin[i]);
    }
}