#include <climits>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX = 100005;
int dist[NMAX];

struct comp {
  bool operator()(int a, int b) { return dist[a] > dist[b]; }
};

bool viz[NMAX];

vector<pair<int, int> > lista[NMAX];

priority_queue<int, vector<int>, comp> pq;

int n, m;

void dijkstra(int x) {
  viz[x] = 1;
  dist[x] = 0;
  pq.push(x);
  while (!pq.empty()) {
    x = pq.top();
    pq.pop();
    viz[x] = 0;
    for (pair<int, int> el : lista[x]) {
      int nod = el.first;
      int cost = el.second;
      if (dist[x] + cost < dist[nod]) {
        dist[nod] = dist[x] + cost;
        if (!viz[nod]) {
          pq.push(nod);
          viz[nod] = 1;
        }
      }
    }
  }
}

int main() {
  int p, i, j, c, x, y, m;
  fin >> n >> m;
  while (m--) {
    fin >> x >> y >> c;
    lista[x].push_back({y, c});
  }

  for (i = 1; i <= n; i++) {
    dist[i] = NMAX;
  }

  dijkstra(1);

  for (i = 1; i <= n; i++) {
    if (dist[i] == NMAX) {
      fout << 0 << ' ';
    } else {
      fout << dist[i] << ' ';
    }
  }
  fin.close();
  fout.close();
  return 0;
}