/// dijkstra


#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;

}