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

using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int Nmax = 50444;

int N, M, a, b, c, d[Nmax];
char inq[Nmax];

vector<pii> G[Nmax];

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

  fin >> N >> M;
  for(int i = 0; i < M; ++i) {
    fin >> a >> b >> c;
    --a, --b;
    G[a].push_back({b, c});
  }

  for(int i = 0; i < N; ++i)
    d[i] = INF;

  d[0] = 0;
  queue<int> Q;
  Q.push(0);
  inq[0] = 1;
  while(!Q.empty()) {
    int x = Q.front(); Q.pop();
    inq[x] = 0;
    for(auto P: G[x]) {
      if(d[P.first] > d[x] + P.second) {
        d[P.first] = d[x] + P.second;
        if (!inq[P.first]){
          inq[P.first] = 1;
          Q.push(P.first);
        }
      }
    }
  }
  for (int i = 1; i < N; ++i)
    fout << (d[i] == INF ? 0 : d[i]) << ' ';
  fout << endl;

  return 0;
}