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

using namespace std;

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

const int MAXN = 50000;
const int INFINIT = 1000000001;

vector<pair<int, int>> g[MAXN + 1];
int dist[MAXN + 1];
priority_queue<pair<int, int>> pq;

void dijkstra(int node) {
  dist[node] = 0;
  pq.push({0, node});
  while(!pq.empty()) {
    pair<int, int> curr = pq.top();
    pq.pop();
    int node = curr.second;
    if(dist[node] == -curr.first) {
      for(auto edge : g[node]) {
        int vecin = edge.first, cost = edge.second;
        if(dist[vecin] > dist[node] + cost) {
          dist[vecin] = dist[node] + cost;
          pq.push({-dist[vecin], vecin});
        }
      }
    }
  }
}

int main() {
  int n, m;
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v, w;
    fin >> u >> v >> w;
    g[u].push_back({v, w});
  }

  for(int i = 1; i <= n; i++) {
    dist[i] = INFINIT;
  }
  dijkstra(1);

  for(int i = 2; i <= n; i++) {
    fout << dist[i] << " ";
  }
  return 0;
}