#include <fstream>
#define pinf 100000000
#define NMAX 50003
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{
    int urm,cost;
    nod *next;
};
nod *p,*l[50003];
int coada[5*NMAX];
int main()
{
    int m,pr,u,i,x,n,d[NMAX];

    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        p=new nod;
        fin>>x>>p->urm>>p->cost;
        p->next=l[x];
        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]<<" ";
    fin.close();
    fout.close();
    return 0;
}