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

struct graf {  int y, cost; } varf;
bool inq[nmax];
int q[nmax*10],dist[nmax],n,m;
vector <graf> c[nmax];

void citire ()
{
  int i,x;
  f>>n>>m;
  for (i=1; i<=m; i++)
  {
    f>>x>>varf.y>>varf.cost;
    c[x].push_back (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=0; i<c[x].size (); i++)
    {
      if (dist[x]+c[x][i].cost < dist [c[x][i].y])
      {
        dist[c[x][i].y]=dist[x]+c[x][i].cost;
        if (!inq[c[x][i].y])
        {
          inq[c[x][i].y]=1;
          q[++u]=c[x][i].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;
}