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

using namespace std;

struct nod {
  int n, d;
}nou;

int n, m, i, a, b, c, dist[50001];
vector<nod> vec[50001];
queue<nod> q;

void init () {
  for (i = 2; i <= n; i++)
    dist[i] = 2e9;
}

bool cmp (nod a, nod b) {
  if (a.d == b.d)
    return a.n < b.n;
  return a.d < b.d;
}

void parcurgere () {
  int i, j, dn;
  nod nc, nn;
  nn.n = 1, nn.d = 0; q.push(nn);
  while (!q.empty()) {
    nc = q.front(); q.pop();
    for (j = 0; j < vec[nc.n].size(); j++) {
      dn = dist[nc.n]+vec[nc.n][j].d;
      if (dist[vec[nc.n][j].n] > dn)
        dist[vec[nc.n][j].n] = dn, nn.n = vec[nc.n][j].n, nn.d = dn, q.push(nn);
    }
  }
}

int main () {
  ifstream fi("dijkstra.in");
  ofstream fo("dijkstra.out");
  fi >> n >> m; init ();
  for (i = 1; i <= m; i++)
    fi >> a >> b >> c, nou.n = b, nou.d = c, vec[a].push_back(nou);
  for (i = 1; i <= n; i++)
    sort(vec[i].begin(), vec[i].end(), cmp);
  parcurgere ();
  for (i = 2; i <= n; i++)
    if (dist[i] == 2e9) fo << 0 << ' ';
    else
    fo << dist[i] << ' ';
  return 0;
}