#include<fstream>
using namespace std;
int n,D[100002],vfstart;
struct nod
{
    int v, cost;
    nod *urm;
};
nod *LA[100002];
int viz[100002],T[100002];
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]=2000000;
    }
    D[vfstart]=0;
    for(i=1;i<=n;i++)
    {
        vmin=2000000;
        for(j=1;j<=n;j++)
        {
            if(D[j]<vmin&&viz[j]==0)
            {
                vmin=D[j];
                poz=j;
            }
        }
        if(vmin==2000000)
        {
            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;
    ofstream fout("dijkstra.out");
    for(i=2;i<=n;i++)
    {
       if(D[i]==2000000)
       {
           fout<<0<<" ";
       }
       else
       {
           fout<<D[i]<<" ";
       }
    }
    fout.close();
}
int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}