#include <bits/stdc++.h>
using namespace std;
const int NMAX = 5e4+2;
const int INF = 1e6;
using pii = pair<int, int>;
int n,m,dist[NMAX];
vector<pii> v[NMAX];

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

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++){
    int x, y, z;
    fin >> x >> y >> z;
    v[x].push_back({y, z});
  }
  for(int i = 1; i <= n; i++){
    dist[i] = INF;
  }
  set<pii> s;
  dist[1] = 0;
  s.insert({0, 1});
  while(!s.empty()){
    int nod = s.begin()->second;
    s.erase(s.begin());
    for(auto [vecin, cost]: v[nod]){
      if(dist[vecin] > dist[nod] + cost){
        s.erase({dist[vecin], vecin});
        dist[vecin] = cost + dist[nod];
        s.insert({dist[vecin], vecin});
      }
    }
  }
  for(int i = 2; i <= n; i++){
    fout << (dist[i] == INF ? 0 : dist[i]) << " ";
  }
  return 0;
}