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

using namespace std;

const int NMAX =  50002;
const int MMAX = 250002;
const int INF = numeric_limits<int>::max();

int N, M;

vector<int> d(NMAX, INF);

vector<vector<pair<int,int>>> graph(NMAX, vector<pair<int, int>>());

int main() {
   ifstream iff ("dijkstra.in");
   ofstream off("dijkstra.out");
   iff >> N >> M;

   for (int i = 0; i < M; ++i) {
      int f, t, m;
      iff >> f >> t >> m;
      graph[f].push_back(make_pair(t, m));
   }

   set<pair<int,int>> s;

   s.insert(make_pair(0, 1));
   d[1] = 0;

   while (!s.empty()) {
      pair<int, int> p = *(s.begin());
      s.erase(p);
      int n = p.second;
      int dist = p.first;
      for (pair<int,int> np : graph[n]) {
         int n_node = np.first;
         int m = np.second;
         if (dist + m < d[n_node]) {
            if (d[n_node] < INF) {
               auto it = s.find(make_pair(d[n_node], n_node));
               s.erase(*it);
            }
            d[n_node] = dist + m;
            s.insert(make_pair(dist + m, n_node));
         }
      }
   }

   for (int i = 2; i <= N; ++i) {
      int p = d[i] == INF ? 0 : d[i];
      off << p << " ";
   }


   return 0;
}