#include <fstream>
#define inf 10000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,s,cost,d[1001],T[1001],k,coada[5001],c[1001][1001],j,i,x,y;
void drum (int x)
{
  if(x!=0)
  {
    drum(T[x]);
    g<<x<<" ";
  }
}
void bellf (int nod)
{
  int p,u,j,i;
  for(i=1;i<=n;i++)
    d[i]=inf;
  d[nod]=0;
  p=u=1;
  coada[u]=nod;
  while(p<=u)
  {
    j=coada[p];
    p++;
    for(i=1;i<=n;i++)
      if(c[j][i]!=inf)
      if(d[i]>d[j]+c[j][i])
    {
      d[i]=d[j]+c[j][i];
      T[i]=j;
      coada[++u]=i;
    }
  }

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