//Algoritmul lui Dijkstra

#include <fstream>
using namespace std;
struct nod{
       int vf, cost;
       nod *next;
} *vecini[50005];
int n,m,d[50005],s[50005];
int infinit=10000001;
void add(nod *&prim,int x,int y)
{
     nod *p=new nod;
     p->vf=x;
     p->cost=y;
     p->next=prim;
     prim=p;
}
void citire()
{
     int i,x,y,z;
     ifstream f("dijkstra.in");
     f>>n>>m;
     for(i=1;i<=m;i++)
     {
      f>>x>>y>>z;
      add(vecini[x],y,z);
     }
     f.close();
}
void disjktra()
{
     int i,j,min,pmin;
     for(i=2;i<=n;i++)
      d[i]=infinit;
     for(i=1;i<=n;i++)
     {
      min=infinit,pmin=0;
      for(j=1;j<=n;j++)
       if(!s[j]&&min>d[j])
        min=d[j],pmin=j;
      s[pmin]=1;
      nod *p=vecini[pmin];
      while(p)
      {
              if(d[p->vf]>d[pmin]+p->cost)
               d[p->vf]=d[pmin]+p->cost;
              p=p->next;
      }
     }
}
void afisare()
{
     ofstream g("dijkstra.out");
     int i;
     for(i=2;i<=n;i++)
      if(d[i]!=infinit)
       g<<d[i]<<" ";
      else
       g<<"0 ";
     g<<"\n";
     g.close(); 
}
int main()
{
    citire();
    disjktra();
    afisare();
    return 0;
}