#include <stdio.h>

#include <vector>
#include <queue>

using namespace std;

int n, m;
vector< vector< pair<int, int> > > lad;
vector<int> d;

struct dcmp {
  const bool operator()(const int &x, const int &y) const {
    return d[x] > d[y];
  }
};
priority_queue<int, vector<int>, dcmp> t;

int main(void) {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  scanf("%d%d", &n, &m);

  lad.resize(n);
  d.resize(n, 1000000000);

  for (int i=0; i<m; ++i) {
    int x, y, c;
    scanf("%d%d%d\n", &x, &y, &c);
    lad[x-1].push_back(pair<int, int>(y-1, c));
  }

  d[0] = 0;
  t.push(0);
  while (t.size() > 0) {
    const int node = t.top();
    t.pop();

    for (const pair<int, int>& l : lad[node]) {
      if (d[l.first] > d[node] + l.second) {
        d[l.first] = d[node] + l.second;
        t.push(l.first);
      }
    }
  }

  for (int i=1; i<n; ++i) {
    printf("%d ", d[i] == 1000000000 ? 0 : d[i]);
  }

  return 0;
}