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

int n,m,a,b,c,i;
int h[50001],d[50001],idx[50001];
int hsize;

int inf=2000000000;
typedef struct celula{

int v;
celula *next;
int dist;
}*lista;

lista g[50001],p;

void downh()
{
    int aux=1;

    while(aux*2<=hsize)
    {
        int index=aux;

        if(d[h[2*aux]]<d[h[aux]]) index=2*aux;
        if(2*aux+1<=hsize)
            if(d[h[2*aux+1]]<d[h[index]]) index=2*aux+1;

        if(index==aux) break;

        swap(idx[h[aux]],idx[h[index]]);
        swap(h[aux],h[index]);

    }

}

void uph(int x)
{
    while(x>1 && d[h[x/2]]>d[h[x]])
    {
        swap(idx[h[x]],idx[h[x/2]]);
        swap(h[x/2], h[x]);
        x/=2;
    }
}


int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;

        p=new celula;
        p->v=b;
        p->dist=c;
        p->next=g[a];
        g[a]=p;

    }

        for(i=1;i<=n;++i)
            h[i]=i,idx[i]=i,d[i]=inf;

        d[1]=0;
        hsize=n;


        while(hsize>0)
        {
            int nodc=h[1];
            idx[h[hsize]]=1;
            h[1]=h[hsize];
            --hsize;
            downh();

            for(lista i=g[nodc];i!=NULL;i=i->next)
                if(d[i->v]>d[nodc]+i->dist)
                {
                  d[i->v]=d[nodc]+i->dist;
                  uph(idx[i->v]);

                }

        }


    for(i=2;i<=n;++i)
        if(d[i]==inf) fout<<"0"<<" ";
        else fout<<d[i]<<" ";

    return 0;
}