#include <iostream>
#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() {
   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]) {
            if (d[n_node] < INF) {
               auto it = s.find(make_pair(n_node, d[n_node]));
               s.erase(*it);
            }
            d[n_node] = dist + m;
            s.insert(make_pair(n_node, dist + m));
         }
      }
   }

   for (int i = 2; i <= N; ++i) {
      int p = d[i] == numeric_limits<int>::max() ? 0 : d[i];
      printf("%d ",p);
   }


   return 0;
}