#include <fstream>
#define pinf 100000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{
    int urm,cost;
    nod *next;
};
nod *p,*l[50003];
int x,y,i,j,n,nods,coada[250003],d[50003],m,st,w,z,pr,u,c;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        p=new nod;
        p->next=l[x];
        p->urm=y;
        p->cost=c;
        l[x]=p;
    }
    pr=1;u=1;
    coada[u]=1;


    for(i=1;i<=n;++i)
            d[i]=pinf;
    d[1]=0;
    while(pr<=u)
    {
        x=coada[pr];
        pr++;
        p=new nod;
        p=l[x];
        while(p)
        {

                if(d[x]+p->cost<d[p->urm])
                    {
                        d[p->urm]=d[x]+p->cost;
                        coada[++u]=p->urm;
                    }
            p=p->next;
        }
    }
    for(i=2;i<=n;++i)
        if(d[i]==pinf)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";

    return 0;
}