#include <stdio.h>
#include <vector>
#include <queue>
#include <limits.h>

#define MAX_N 50000

using std::vector;
using std::priority_queue;
using std::pair;
using std::make_pair;

struct MinHeap{
  bool operator()(pair <int, int> a, pair <int, int> b) {
    if (a.second < b.second)
      return 0;
    return 1;
  }
};

priority_queue<pair<int, int>,vector<pair<int, int> >, MinHeap> heap;

int N, M;
int dist[MAX_N + 1];

struct cell {
  int node;
  int cost;
};

vector <cell> graf[MAX_N + 1];
vector <cell> ::iterator it;

void init() {
  int i;
  for (i = 1; i <= N; i++)
    dist[i] = INT_MAX;
}

void Djikstra(int S) {
  int node_curr, cost_curr;

  init();

  dist[S] = 0;
  heap.push(make_pair(S, 0));
  while (!heap.empty()) {
    pair<int, int> curr = heap.top();
    node_curr = curr.first;
    cost_curr = curr.second;
    heap.pop();
    if (dist[node_curr] == cost_curr) {
      for (it = graf[node_curr].begin(); it != graf[node_curr].end(); it++) {
        if (dist[it->node] > dist[node_curr] + it->cost) {
          dist[it->node] = dist[node_curr] + it->cost;
          heap.push(make_pair(it->node, dist[it->node]));
        }
      }
    }
  }
}

int main(){

  FILE *fin = fopen("dijkstra.in", "r");
  FILE *fout = fopen("dijkstra.out", "w");

  int i, j;
  int x, y, cost;

  fscanf(fin, "%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    fscanf(fin, "%d %d %d", &x, &y, &cost);
    graf[x].push_back((cell){y, cost});
  }

  Djikstra(1);

  for (i = 2; i <= N; i++)
    fprintf(fout, "%d ", dist[i] == INT_MAX ? 0 : dist[i]);
  fprintf(fout, "\n");

  return 0;
}