#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct nod {
  int n, d, c;
};

struct cmp {
  bool operator()(const nod &a, const nod &b) const {
    return (a.d > b.d);
  }
};

int n, m, dist[50005], x;
bool viz[50005];
vector<nod>vec[50005];
priority_queue<nod, vector<nod>, cmp>q;

void dijkstra(int sursa) {
  nod nodc;

  dist[sursa] = 0;
  nodc.n = sursa, nodc.d = 0;
  q.push(nodc);
  while (!q.empty()) {
    nodc = q.top(); q.pop();
    if (viz[nodc.n])
      continue;
    viz[nodc.n] = true;
    vector<nod>::iterator i;
    for (i = vec[nodc.n].begin(); i < vec[nodc.n].end(); i++)
      if (!viz[(*i).n]) {
        int dn = dist[nodc.n]+(*i).c;
        if (dn < dist[(*i).n]) {
          dist[(*i).n] = dn; nod vecin;
          vecin.n = (*i).n; vecin.d = dn;
          q.push(vecin);
        }
      }
  }
}

int main () {
  ifstream fi("dijkstra.in");
  ofstream fo("dijkstra.out");
  fi >> n >> m;
  for (int i = 1; i <= n; i++)
    dist[i] = 2e9;
  nod vecin;
  for (int i = 1; i <= m; i++)
    fi >> x >> vecin.n >> vecin.c, vec[x].push_back(vecin);
  dijkstra(1);
  for (int i = 2; i <= n; i++)
    dist[i] == 2e9 ? fo << "0 " : fo << dist[i] << ' ';
  return 0;
}