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

using namespace std;

const int NMAX =  50002;
const int MMAX = 250002;

int N, M;

vector<int> d(NMAX, numeric_limits<int>::max());

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

int main() {
   freopen("dijkstra.in", "r", stdin);
   freopen("dijkstra.out", "w", stdout);

   scanf("%d %d", &N, &M);

   for (int i = 0; i < M; ++i) {
      int f, t, m;
      scanf("%d %d %d", &f, &t, &m);
      graph[f].push_back(make_pair(t, m));
   }

   set<pair<int,int>> s;

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

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

   for (int i = 2; i <= N; ++i) {
      printf("%d ",d[i]);
   }


   return 0;
}