#include <iostream>
#include <stdio.h>
#include <vector>

#define MAXN 50003
#define INF (1 << 30)
#define inFile "dijkstra.in"
#define outFile "dijkstra.out"

using namespace std;

int H[MAXN],K; /* Heapul si Numarul de elem din Heap */
int poz[MAXN]; /* Poz din H in care apare H[i] */
int d[MAXN];   /* Distanta minima de la nodul de plecare la restul nodurilor */

int N, M;

struct obj { int x, z; };

vector<obj> G[MAXN];

inline void add(int x, int y, int z)
{
  G[x].push_back({y, z});
}

void read(void)
{
  FILE * f = fopen(inFile, "r");
  fscanf(f, "%d %d", &N, &M);
  for (int i = 1, x, y, z; i <= M; i++)
  {
    fscanf(f, "%d %d %d", &x, &y, &z);
    add(x,y,z);
  }
  fclose(f);
}

void Jos(int k, int n)
{
  int Fiu;
  while (true)
  {
    Fiu = 0;
    if ((k << 1) <= n) Fiu = (k << 1);
    if ((k << 1) + 1 <= n && d[ H[Fiu] ] < d[ H[Fiu] ]) Fiu = (k << 1) + 1;
    if (d[ H[k] ] > d[ H[Fiu] ] && Fiu)
    {
      poz[ H[k] ] = Fiu;
      poz[ H[Fiu] ] = k;

      swap(H[k], H[Fiu]);
      k = Fiu;
    }
    else return;
  }
}

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

void dijkstra()
{
  for (int i = 2; i <= N; i++)
    d[i] = INF, poz[i] = -1;

  d[1] = 0;
  H[++K] = 1;
  poz[1] = 1;

  while (K)
  {
    int min = H[1];
    swap(H[1], H[K]);
    poz[ H[1] ] = 1;
    K--;

    Jos(1, K);

    int nod = min;
    for (vector<obj>::iterator i = G[nod].begin(); i != G[nod].end(); i++)
    {
      int x = (*i).x;
      int z = (*i).z;
      if (d[x] > d[nod] + z)
      {
        d[x] = d[nod] + z;
        if (poz[x] != -1)
        {
          Sus(poz[x]);
        }
        else
        {
          H[++K] = x;
          poz[ H[K] ] = K;
          Sus(K);
        }
      }
    }
  }
}

void write(void)
{
  FILE * g = fopen(outFile, "w");
  for (int i = 2; i <= N; i++)
  {
    fprintf(g, "%d ", d[i] == INF ? 0 : d[i]);
  }
  fclose(g);
}

int main()
{
  read();
  dijkstra();
  write();
  return 0;
}