#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 5e4;
const ll inf = 1e15;

vector<vector<pair<ll, int>>> dx(nmax+5);
int n, m;
ll dp[nmax+5];

void dijkstra(int start) {
  for(int i=1; i<=n; i++) dp[i] = inf;
  dp[start] = 0;
  priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
  pq.emplace(0, 1);
  while(pq.empty() == false) {
    pair<int, int> now = pq.top(); pq.pop();
    if(now.first != dp[now.second]) continue;

    for(auto nxt : dx[now.second])
      if(now.first + nxt.first < dp[nxt.second]) {
        dp[nxt.second] = now.first + nxt.first;
        pq.emplace(now.first + nxt.first, nxt.second);
      }
  }
}

int main() {
  ifstream f("dijkstra.in");
  ofstream g("dijkstra.out");
  
  f >> n >> m;
  for(int i=1; i<=m; i++) {
    int x, y, cost; f >> x >> y >> cost;
    dx[x].emplace_back(cost, y);
  }
  dijkstra(1);
  for(int i=2; i<=n; i++) g << dp[i] << " ";
  return 0;
}