#include <iostream>
#include <queue>
#include <vector>

#define MAXN 50000
#define INF 1000000000

using namespace std;

struct edge{
  int b, cost;
};

inline bool operator< (edge a, edge b) {
  return a.cost > b.cost;
}

priority_queue <edge> q;
vector <edge> graph[MAXN];
int minDist[MAXN];

void addEdge(int a, int b, int cost) {
  graph[a].push_back({b, cost});
}

void dijkstra(int n) {
  int i, node, x;

  for ( i = 1; i < n; i++ ) {
    minDist[i] = INF;
  }

  minDist[0] = 0;
  for ( edge x : graph[0] ) {
    q.push(x);
  }

  x = 1;
  while ( q.size() && x < n ) {
    if ( minDist[q.top().b] > q.top().cost ) {
      minDist[q.top().b] = q.top().cost;
      node = q.top().b;
      q.pop();
      x++;

      for ( edge x : graph[node] ) {
        if ( minDist[x.b] > minDist[node] + x.cost ) {
          q.push({x.b, minDist[node] + x.cost});
        }
      }
    } else {
      q.pop();
    }
  }
}

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

  int n, m, i, a, b, c;

  fscanf(fin, "%d%d", &n, &m);

  for ( i = 0; i < m; i++) {
    fscanf(fin, "%d%d%d", &a, &b, &c);

    addEdge(a - 1, b - 1, c);
  }

  dijkstra(n);

  for ( i = 1; i < n; i++ ) {
    fprintf(fout, "%d ", minDist[i]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}