#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,j,u,v,viz[50009],cd[50009],pr,ul,d[50009],nr,c;
struct nod
{
    int vecin,cost;
    nod *adr;
};
nod *lv[50009],*p;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v>>c;
        p=new nod;
        p->vecin=v;
        p->cost=c;
        p->adr=lv[u];
        lv[u]=p;
    }
    for(i=1;i<=n;i++)
    {
        d[i]=100000000;
        viz[i]=0;
    }
    d[1]=0;
    cd[1]=1;
    pr=1;
    ul=1;
    viz[1]=1;
    nr=1;
    while(nr!=0)
    {
        u=cd[pr];
        for(p=lv[u];p!=0;p=p->adr)
        {
            v=p->vecin;
            c=p->cost;
            if(d[u]+c<d[v])
            {
                d[v]=d[u]+c;
                if(viz[v]==0)
                {
                    ul++;
                    if(ul>50000)
                        ul=1;
                    cd[ul]=v;
                    viz[v]=1;
                    nr++;
                }
            }
        }
        pr++;
        if(pr>50000)
            pr=1;
        nr--;
        viz[u]=0;
    }
    for(i=2;i<=n;i++)
        if(d[i]==100000000)
            fout<<"0 ";
        else fout<<d[i]<<" ";
        return 0;
}