#include <stdio.h>

#include <vector>
#include <queue>

using namespace std;

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

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

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

//  for (int i=0; i<n; ++i)
//    lad.push_back(vector< pair<int, int> > ());
  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(make_pair(y-1, c));
  }

  t.push(make_pair(0, 0));
  d[0] = 0;

  while (t.size() > 0) {
    const pair<int, int> &front = t.top();
    int dist = front.first;
    int node = front.second;
    t.pop();

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

    /*
    for (vector<pair<int, int> >::const_iterator l = lad[node].begin(); l != lad[node].end(); ++l) {
      if (d[l->first] > dist + l->second) {
        d[l->first] = dist + l->second;
        t.push(make_pair(d[l->first], l->first));
      }
    }
    */

  }

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

  return 0;
}