#include <bits/stdc++.h>

using namespace std;

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

const int NM = 5e4 + 5;

vector<pair<int, int>>g[NM];
int d[NM], n, m;

int main(){
  fin >> n >> m;
  for (int i = 0; i < m; i++){
    int x, y, cost; fin >> x >> y >> cost;
    g[x].push_back({y, cost});
  }
  fill(d + 1, d + n + 1, 1e9);
  d[1] = 0;
  set<pair<int, int>>mySet;
  mySet.insert({0, 1});
  while (!mySet.empty()){
    int nod = mySet.begin() -> second, cost = mySet.begin() -> first;
    mySet.erase(mySet.begin());
    if (d[nod] < cost){
      continue;
    }
    for (pair<int, int>x : g[nod]){
      if (d[x.first] > d[nod] + x.second){
        d[x.first] = d[nod] + x.second;
        mySet.insert({d[x.first], x.first});
      }
    }
  }
  for (int i = 2; i <= n; i++){
    if (d[i] == 1e9){
      d[i] = 0;
    }
    fout << d[i] << " ";
  }
}