#include <bits/stdc++.h>
using namespace std;
typedef long long i8;
i8 n;
vector<i8> dj(vector<vector<i8>>& v) {
  vector<bool> vst(n, false);
  vector<i8> lng(n, INT64_MAX);
  lng[0] = 0;
  for (int i = 0; i < n; i++) {
    i8 mn = -1;
    for (int j = 0; j < n; j++) {  // find the next node to start with
      if (!vst[j] && (mn == -1 || lng[mn] > lng[j])) {
        mn = j;
      }
    }
    if (mn == -1 || lng[mn] == INT64_MAX) {
      break;
    }
    for (int j = 0; j < n; j++) {
      if (v[mn][j] != -1) {
        lng[j] = min(lng[j], lng[mn] + v[mn][j]);
      }
    }
    vst[mn] = true;
  }
  return lng;
}
int main() {
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");
  i8 m;
  cin >> n >> m;

  vector<vector<i8>> v(n, vector<i8>(n, -1));

  for (int i = 0; i < m; i++) {
    i8 a, b, c;
    cin >> a >> b >> c;
    v[a - 1][b - 1] = c;
  }
  vector<i8> djk = dj(v);
  for (int i = 1; i < n; i++) {
    if (djk[i] == INT64_MAX) {
      cout << 0 << " ";
    } else
      cout << djk[i] << " ";
  }
}