#include <bits/stdc++.h>
 
using namespace std;

const int INF = 0x3f3f3f3f;

struct Graph {
  int n;
  vector<vector<pair<int, int>>> adj;
  
  Graph(int n) : n(n), adj(n) {}
 
  void AddEdge(int a, int b, int c) {
    adj[a].emplace_back(b, c);
  }
 
  vector<int> Dijkstra(int source) {
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>> pq;
 
    pq.emplace(0, source);
 
    while (!pq.empty()) {
      int d, node; 
      tie(d, node) = pq.top(); 
      pq.pop();
      d = -d;
      
      if (d > dist[node]) continue;
 
      for (auto edge : adj[node]) {
        int nei, cost; 
        tie(nei, cost) = edge;

        if (d + cost < dist[nei]) {
          dist[nei] = d + cost;
          pq.emplace(-(d + cost), nei);
        }
      }
    }
 
    return dist;
  }
};
 
int main(){
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");
  
  int n, m; 
  cin >> n >> m;
  
  Graph graph(n);
  
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c; --a; --b;

    graph.AddEdge(a, b, c);
  }
  
  vector<int> dist = graph.Dijkstra(0);
  for (int i = 1; i < n; ++i) {
    if (dist[i] == INF) {
      cout << "0 ";
    } else {
      cout << dist[i] << " ";
    }
  }
  cout << endl;

  return 0;
}