#include <fstream>
#include <queue>
#include <vector>
#include <climits>


using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int nmax = 50005;
vector<pair<int, int>> l[nmax];
vector<int> sol(nmax, INT_MAX);

int n, m;
void solve(int start){
  priority_queue<pair<int, int>> q; // retinem in primul lungimea pana la el cu minus iar in partea a doua punctul in sine
  q.push({0, 1});
  while(!q.empty()){
    int node = q.top().second, dist = -q.top().first;
    if(dist > sol[node]){
      continue;
    }
    q.pop();
    for(auto x: l[node]){
        int vec = x.first;
        if(sol[vec] > sol[node] + x.second){
          sol[vec] = sol[node] + x.second;
          q.push({-sol[vec], vec});
        }
    }
  }
}

int main(){
  f >> n >> m;
  for(int i = 1; i <= m; i++){
    int x, y, z;
    f >> x >> y >> z;
    l[x].push_back({y, z});
  }
  sol[1] = 0;
  solve(1);
  for(int i = 2; i <= n; i++){
    g << sol[i] << ' ' ;
  }
}