#include <bits/stdc++.h>

#define N 50005 
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
int dp[N];
vector<pair<int, int>> graf[N];

void read() {
  f>>n>>m;
  int x, y, z;
  for(int i = 1;i <= m;++i) {
    f>>x>>y>>z;
    graf[x].push_back(make_pair(y, z));
  }
  f.close();
}

void solve() {
  set<pair<int, int>> h;
  h.insert(make_pair(0, 1));
  memset(dp, oo, sizeof(dp));
  dp[1] = 0;

  while(!h.empty()) {
    int nod = h.begin()->second;
    h.erase(h.begin());

    for(const auto& pr : graf[nod]) {
      if(dp[pr.first] > dp[nod] + pr.second) {
        if(dp[pr.first] != oo) {
          h.erase(h.find(make_pair(dp[pr.first], pr.first)));
        }

        dp[pr.first] = dp[nod] + pr.second;
        h.insert(make_pair(dp[pr.first], pr.first));
      }
    }
  }
  for(int i = 2;i <= n;++i) {
    g<<(dp[i] == oo ? 0 : dp[i])<<" ";
  }
}


int main() {
  read();
  solve();
  return 0;
}