#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
const int NMAX = 50005;
const int INF = 0x3f3f3f3f;

struct edge {
  int to, cost;
};
struct entry {
  int node, cost;
};
int n, m;
vector <edge> G[NMAX];
bool processed[NMAX];

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

void solve() {
  // init distances
  vector<int> D(n + 1, INF);
  D[1] = 0;
  
  // init priority queue
  auto func = [&](const entry& a, const entry& b) -> bool {
    return a.cost > b.cost;
  };
  priority_queue<entry, vector<entry>, decltype(func)> Q(func);
  Q.push({1, 0});
  
  while (!Q.empty()) {
    entry a = Q.top();
    Q.pop();
    if (processed[a.node]) {
      continue ;
    }
    processed[a.node] = true;
    // expand
    for (auto it = G[a.node].begin(); it != G[a.node].end(); it++) {
      if (D[it -> to] > a.cost + (it -> cost)) {
        D[it -> to] = a.cost + (it -> cost);
        Q.push({it -> to, D[it -> to]});
      }
    }
  }
  
  for (int i = 2; i <= n; i++) {
    printf("%d", D[i] == INF ? 0 : D[i]);
    if (i < n) printf(" ");
  }
}

int main() {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  
  read();
  solve();
  return 0;
}