#include <fstream>
#define nmax 50002
#define inf 1
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct graf {  int y, cost; } **c=0,varf;
bool inq[nmax];
int q[nmax],dist[nmax],nrvecini[nmax],nrv[nmax],n,m;

void citire ()
{
  int i,x,y,cost;
  f>>n>>m;
  for (i=1; i<=m; i++)
  {
    f>>x>>y>>cost;
    nrvecini[x]++;
  }
  f.seekg(0,ios::beg);
  f.clear();
  c=new graf *[n+1];
  for (i=1; i<=n; i++)
  {
    c[i]=new  graf [nrvecini[i]+1];
    memset (c[i],0,(nrvecini[i]+1)*sizeof(*c[i]));
  }
  f>>n>>m;
  for (i=1; i<=m; i++)
  {
    f>>x>>y>>cost;
    varf.y=y;
    varf.cost=cost;
    c[x][++nrv[x]]=varf;
  }
  f.close ();
}

void Bellman_Ford ()
{
  int p,u,i,x;
  memset (dist,inf,sizeof(dist));
  memset (inq,false,sizeof(inq));
  dist[1]=0;
  p=u=1;
  q[p]=1; // q = coada;
  inq[1]=1;
  while (p<=u)
  {
    x=q[p];
    inq[x]=0;
    p++;
    for (i=1; i<=nrvecini[x]; i++)
    {
      varf=(c[x][i]);
      if (dist[x]+varf.cost < dist [varf.y])
      {
        dist[varf.y]=dist[x]+varf.cost;
        if (!inq[varf.y])
        {
          inq[varf.y]=1;
          q[++u]=varf.y;
        }
      }
    }
  }
}

void afisare ()
{
  for (int i=2; i<=n; i++)
    g<<(dist[i]>=100000?0:dist[i])<<" ";
  g.close ();
}
  
int main ()
{
  citire ();
  Bellman_Ford ();
  afisare ();
  return 0;
}