#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#define Nmax 50005
#define INF (int)1e9
#define InFile "dijkstra.in"
#define OutFile "dijkstra.out"
#define pb push_back

using namespace std;

int n, m, lgh;
int d[Nmax], H[Nmax], poz[Nmax];
vector <int> A[Nmax], C[Nmax];

void read();
void Dijkstra();
void insert (int);
void upheap(int);
int extract();
void downheap(int);
void write();

int main()
{
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  Dijkstra();
  write();
  return 0;
}

void read()
{
  int i, x, y, c;
  scanf ("%d %d\n", &n, &m);
  for (i=1; i<=m; i++)
  {
    scanf ("%d %d %d\n", &x, &y, &c);
    A[x].pb(y);
    C[x].pb(c);
  }
}

void Dijkstra()
{
  int i, lg, vfm, x, c, nr;
  for (i=1; i<=n; i++) d[i]=INF, poz[i]=-1;
  lg=A[1].size();
  d[1]=0;
  for (i=0; i<lg; i++) d[A[1][i]]=C[1][i];
  for (i=1; i<=n; i++)
    insert (i);
  nr=n;
  while (nr)
  {
    //scot minimu
    vfm=extract();
    poz[vfm]=-1;
    lg=A[vfm].size();
    for (i=0; i<lg; i++)
    {
      x=A[vfm][i]; c=C[vfm][i];
      if (poz[x]!=-1)
        if (d[x]>d[vfm]+c)
        {
          d[x]=d[vfm]+c;
          upheap (poz[x]);
        }
    }
	nr--;
  }
}

void insert (int nd)
{
  H[++lgh]=nd;
  poz[nd]=lgh;
  upheap (lgh);
}

void upheap (int k)
{
  int key;
  key=H[k];
  while (k>1 && d[key]<d[H[k/2]])
  {
    swap (H[k], H[k/2]);
    k=k/2;
  }
  H[k]=key;
  poz[key]=k;
}

int extract ()
{
  int key=H[1];
  swap (H[1], H[lgh--]);
  downheap(1);
  return key;
}

void downheap(int k)
{
  int key, son, gata=0;
  key=H[k];
  while (!gata)
  {
    son=0;
    if (2*k<=lgh) son=2*k;
    if (2*k+1<=lgh && d[H[2*k]]>d[H[2*k+1]])
      son=2*k+1;
    if (!son || H[k]<H[son])
      gata=1;
    else
		if (H[k]>H[son])
		{
		  swap (H[k], H[son]);
		  k=son;
		}
  }
  H[k]=key;
  poz[key]=k;
}

void write()
{
  int i;
  for (i=2; i<=n; i++)
    if (d[i]!=INF) printf ("%d ", d[i]);
    else printf ("0 ");
  printf ("\n");
}