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

using namespace std;

struct nod {
  int n, d;
};

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

int n, m, d[50001];
bool viz[50001];
vector<int>vec[50001], cost[50001];
priority_queue<nod, vector<nod>, cmp>q;

void initdist () {
  for (int i = 1; i <= n; i++)
    d[i] = 2e9;
}

void dijkstra (int sursa) {
  nod nod, nodc;
  int dn, v, i;

  d[sursa] = 0;
  nod.n = sursa, nod.d = 0, q.push(nod);
  while (!q.empty()) {
    nodc = q.top(); q.pop(); viz[nodc.n] = 1;
    for (i = 0; i < vec[nodc.n].size(); i++) {
      v = vec[nodc.n][i];
      if (!viz[v]) {
        dn = d[nodc.n] + cost[nodc.n][i];
        if (dn < d[v])
          d[v] = dn, nod.n = v, nod.d = d[v], q.push(nod);
      }
    }
  }
}

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