#include<cstdio>
#include<fstream>
#define Nmx 50001
#define INF 1<<20

using namespace std;
int n,m,C[Nmx],poz[4*Nmx],nr,H[Nmx*4];
struct nod
{
    int inf,cost;
    nod *urm;
};
nod *G[Nmx];
ifstream fin("dijkstra.in");

void add(int x,int y,int c)
{
    nod *aux=new nod;
    aux->inf = y;
    aux->cost = c;
    aux->urm = G[x];
    G[x] = aux;
}

void citire()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        add(x,y,c);
    }
}

void down(int k)
{
    while(k*2<=nr)
    {
        int p=k*2;
        if(p+1<=nr)
            if(C[H[p+1]]<C[H[p]])
                p=p+1;
        int aux = poz[H[k]];
        poz[H[k]] = poz[H[p]];
        poz[H[p]] = aux;
        aux = H[k];
        H[k]=H[p];
        H[p]=aux;
        k=p;
    }
}

void up(int k)
{
    while(k>1)
    {
        if(C[H[k/2]]>=C[H[k]])
            return;
        int aux = poz[H[k]];
        poz[H[k]] = poz[H[k/2]];
        poz[H[k/2]] = aux;
        aux = H[k];
        H[k]=H[k/2];
        H[k/2]=aux;
        k=k/2;
    }
}

void solve()
{
    int x;
    for(int i=2;i<=n;++i)
    {
        C[i]=INF;
        poz[i]=-1;
    }
    C[1]=0;
    H[1]=1;
    poz[1]=1;
    nr = 1;
    while(nr)
    {
        int x = H[1];
        poz[H[nr]]=1;
        poz[H[1]]=-1;
        H[1]=H[nr--];
        down(1);
        for(nod *p=G[x];p;p=p->urm)
            if(p->cost+C[x]<C[p->inf])
            {
                C[p->inf]=p->cost+C[x];
                if(poz[p->inf]==-1)
                {
                    H[++nr]=p->inf;
                    poz[p->inf]=nr;
                    up(nr);
                }
                else up(poz[p->inf]);
            }
    }
}

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

int main()
{
    freopen("dijkstra.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}