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

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

const int N = 50005;
const int INF = 0x3f3f3f3f;

vector<pair<int, int> > v[N];
int dist[N];
bool viz[N];

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

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

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

int main() {
  int n, m, i, j, x, y, c;
  fin >> n >> m;

  for (i = 1; i <= m; i++) {
    fin >> x >> y >> c;
    v[x].push_back({y, c});
  }

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

  Dijktra(1);

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