#include <bits/stdc++.h>

using namespace std;
const int MAXM = 5e4;
const int INF = 1e9 + 20;
int n;

vector < pair < int, int > > G[MAXM + 1];
priority_queue <pair <int,int>, vector < pair <int,int> > ,greater <pair <int,int> > > heap;

int dist[MAXM];
void dijkstra (int start) {
  int son, cost, node, distson;
  for (int i = 1; i <= n; i++) {
    dist[i] = INF;
  }
  dist[start] = 0;
  heap.push ({0, start});
  while (heap.empty() != 0) {
    node = heap.top().second;
    cost = heap.top().first;
    heap.pop();
    if (cost <= dist[node]) {
      for (unsigned i = 0; i < G[node].size(); i++) {
        son = G[node][i].first;
        distson = G[node][i].second;
        if (dist[son] > cost + distson) {
          dist[son] = cost + distson;
          heap.push ({dist[son], son});
        }
      }
    }
  }
}

int main()
{
  FILE *fin, *fout;
  int m, i, x, y, cost;
  fin = fopen ("djikstra.in", "r");
  fout = fopen ("djikstra.out", "w");
  fscanf (fin, "%d%d", &n, &m);
  for (i = 0; i < m; i++) {
    fscanf (fin, "%d%d%d", &x, &y, &cost);
    G[x].push_back((make_pair (y, cost)));
  }
  dijkstra(1);
  for (i = 2; i <= n; i++){
    if (dist[i] != INF)
      fprintf (fout, "%d ", dist[i]);
    else
      fprintf (fout, "0 ");
  }
  fclose (fin);
  fclose (fout);
  return 0;
}