#include <fstream>
using namespace std;
struct nod2
{
    int vecin, cost;
    nod2 *leg;
};
nod2 *LV[50002], *p;
int coada[50002],d[50002],viz[50002],pr,ul,nr,c;
int x,y,n,m;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main ()
{
    int i;
   fin>>n>>m;
   for(i=1;i<=m;i++)
   {
        fin>>x>>y>>c;
        p=new nod2;
        p->vecin=y;
        p->cost=c;
        p->leg=LV[x];
        LV[x]=p;
   }
   for(i=1;i<=n;i++)
   {
        d[i]=1000000000;
        viz[i]=0;
   }
   d[1]=0;
   viz[1]=1;
   coada[1]=1;
   pr=1;
   ul=1;
   nr=1;
   while(nr!=0)
   {
        x=coada[pr];
        for(p=LV[x];p!=0;p=p->leg)
        {
            y=p->vecin;
            c=p->cost;
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                if(viz[y]==0)
                {
                    nr++;
                    ul++;
                    if(ul>50000)
                    {
                        ul=1;
                    }
                    coada[ul]=y;
                    viz[y]=1;
                }
            }
        }
        pr++;
        nr--;
        if(pr>50000)
        {
            pr=1;
        }
   }
   for(i=2;i<=n;i++)
   {
        if(d[i]==1000000000)
        {
            d[i]=0;
        }
        fout<<d[i]<<" ";
   }
   fin.close();
   fout.close();
   return 0;
}