#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int N = 1e5;

int n, m, s = 0, d[N];
vector<int> c[N], w[N];

void relax( int &a, int b ) { a = min(a, b); }

int main() {

  scanf("%d%d", &n, &m);
  forn(i, m) {
    int a, b, x;
    scanf("%d%d%d", &a, &b, &x);
    c[a].push_back(b);
    w[a].push_back(x);
  }

  forn(i, n)
    d[i] = INT_MAX / 2;
  d[s] = 0;

  forn(_, n)
    forn(v, n)
      forn(i, c[v].size())
        relax(d[c[v][i]], d[v] + w[v][i]);

  forn(i, n)
    printf("%d ", d[i]);
  return 0;
}