#include<fstream>
using namespace std;
int n,D[100001],vfstart;
int viz[100001],T[100001];
struct nod
{
    int v,cost;
    nod * urm;
};
nod* LA[100001];

void citire()
{
    int m,i,a,b,c;
    nod*p;
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        p=new nod;
        p->v=b;
        p->cost=c;
        p->urm=LA[a];
        LA[a]=p;
    }
    fin.close();
}

void dijkstra()
{
    int i,j,vmin,poz;
    nod*p;
    vfstart=1;
    for(i=1;i<=n;i++)
    {D[i]=1000000;}
    D[vfstart]=0;
    for(i=1;i<n;i++)
    {
        vmin=1000000;
        for(j=1;j<=n;j++)
        {
            if(D[j]<vmin && viz[j]==0)
            {
                vmin=D[j];
                poz=j;
            }
        }
        if (vmin==1000000)
        {break;}
        viz[poz]=1;

        for(p=LA[poz];p!=0;p=p->urm)
        {
            j=p->v;
            if(D[j]>D[poz]+p->cost)
            {
                D[j]=D[poz]+p->cost;
                T[j]=poz;
            }
        }
    }
}

void afisare()
{
    int i,j;
    ofstream fout("dijkstra.out");
    for(i=2;i<=n;i++)
    {
        if(D[i]==1000000)
        {fout<<0<<" ";}
        else
        {fout<<D[j]<<" ";}
    }
    fout.close();
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}