#include <fstream>
#define inf 10000000
#define TU 50005
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int Nod,n,s,cost,d[1001],T[1001],k,coada[5001],j,i,x,y,pr;
struct nod{
  int info; int cost; nod *urm;};
nod *L[TU];
void adauga(int i,int j, int cc){
  nod *p=new nod;
  p->info=j;
  p->cost=cc;
  p->urm=L[i];
  L[i]=p;
}
void bellf (int Nod)
{
  int p,u,j,i;
  for(i=1;i<=n;i++)
    d[i]=inf;
  d[Nod]=0;
  pr=u=1;
  coada[u]=Nod;
  while(pr<=u)
  {
    j=coada[pr];
    pr++;
    nod *p=new nod;
    p=L[j];
    while(p!=0)
    {
      if(d[p->info]>d[j]+p->cost)
    {
      d[p->info]=d[j]+p->cost;

      coada[++u]=p->info;
    }
    p=p->urm;}
  }

}
int main()
{
f>>n>>k;

  for(i=1;i<=k;i++)
  {
    f>>x>>y>>cost;
    adauga(x,y,cost);
  }
  bellf(1);
    for(i=2;i<=n;i++)
      if(d[i]==inf)
      g<<0<<" ";
    else g<<d[i]<<" ";
    return 0;
}