#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <set>

using namespace std;
#define oo 0x3f3f3f3f
#define cost first 
#define ngh second 

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
int dp[50001];
vector<pair<int, int>> graph[50001];

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

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

  while(!h.empty()) {
    auto top = *h.begin();
    h.erase(h.begin());
    
    for(const auto& kv : graph[top.ngh]) {
      if(dp[kv.ngh] > top.cost + kv.cost) {
        if(dp[kv.ngh] != oo) {
          h.erase(h.find({dp[kv.ngh], kv.ngh}));
        }

        dp[kv.ngh] = top.cost + kv.cost;
        h.insert({dp[kv.ngh], kv.ngh});
      }
    }
  }

  for(int i = 2;i <= n;++i) {
    g<<(dp[i] == oo ? 0 : dp[i])<<" ";
  }
}

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