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

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

signed 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;
  }
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  dist[1] = 0;
  pq.push({0, 1});
  while(!pq.empty()){
    auto [accum, nod] = pq.top();
    vis[nod] = true;
    pq.pop();
    for(auto [vecin, cost]: v[nod]){
      if(!vis[vecin] && dist[vecin] > accum + cost){
        dist[vecin] = accum + cost;
        pq.push({dist[vecin], vecin});
      }
    }
  }
  for(int i = 2; i <= n; i++){
    fout << (dist[i] == INF ? 0 : dist[i]) << " ";
  }
  return 0;
}