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

using namespace std;

#define INF 1000000

class graph {
  int vertices;
  int edges;
  vector<vector<pair<int, int>>> adj;
  vector<int> dist;

public:
  graph(int n, int m) : vertices(n), edges(m), adj(n), dist(n, INF) {};
  void read_neighbours(istream& in) {
    int v1, v2, w;
    for (int i = 0; i < edges; i++) {
      in >> v1 >> v2 >> w;
      adj[v1 - 1].push_back(make_pair(v2 - 1, w));
    }
  }
  void dijkstra(int src) {
    set<pair<int, int>> staiLaRand;
    dist[src] = 0;
    for (int i = 0; i < vertices; i++) {
      staiLaRand.insert(make_pair(i, dist[i]));
    }
    while (!staiLaRand.empty()) {
      auto popped = (staiLaRand.begin())->first;
      staiLaRand.erase(staiLaRand.begin());
      for (auto neighbour : adj[popped]) {
        int alt = dist[popped] + neighbour.second;
        if (alt < dist[neighbour.first]) {
          dist[neighbour.first] = alt;
          staiLaRand.erase(make_pair(neighbour.first, dist[neighbour.first]));
          staiLaRand.insert(make_pair(neighbour.first, dist[neighbour.first]));
        }
      }
    }
  }
  void printDistances(ostream& out) {
    for (int i = 1; i < vertices; i++) {
      if (dist[i] != INF)
        out << dist[i] << ' ';
      else
        out << "0 ";
    }
  }
};

int main() {
  int n, m;
  ifstream in("dijkstra.in");
  in >> n >> m;
  graph G(n, m);
  G.read_neighbours(in);
  in.close();
  G.dijkstra(0);
  ofstream out("dijkstra.out");
  G.printDistances(out);
  return 0;
}