#include<fstream>
using namespace std;
int n,m,i,k,x,y,val,viz[50002],s,poz,cost1[50002],tata[50002],dmin;
struct nod
{
    int x,cost;
    nod *leg;
};
nod *p,*v[50002];
int main()
{
     ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>val;
        p=new nod;
        p->x=y;
        p->cost=val;
        p->leg=v[x];
        v[x]=p;
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        cost1[i]=2000000;
        tata[i]=-1;
    }
    cost1[1]=0;
    tata[1]=0;
    for(k=1;k<=n-1;k++)
    {
        dmin=2000000;
        for(i=1;i<=n;i++)
        {
            if(cost1[i]<dmin && viz[i]==0)
            {
                dmin=cost1[i];
                poz=i;
            }
        }
        viz[poz]=1;
        for(p=v[poz];p!=0;p=p->leg)
        {
            if(viz[p->x]==0 && cost1[poz]+p->cost<cost1[p->x])
            {
                cost1[p->x]=cost1[poz]+p->cost;
                tata[p->x]=poz;
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(cost1[i]==2000000)
        {
            fout<<"0"<<" ";
        }
        else
        {
            fout<<cost1[i]<<" ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}