#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

constexpr int INF = 0x3f3f3f3f;

typedef pair<int, int> pcy;


int N, M, x, y, c, D[50003];
vector<pair<int, int>> G[50003];
priority_queue<pcy, vector<pcy>, greater<pcy>> Q;

bool sel[50003];


void dijkstra(int pl);

int main() {

   f >> N >> M;
   for(int i = 1; i <= N; i++) {
      f >> x >> y >> c;
      G[x].push_back({c, y});
   }

   dijkstra(1);

   for(int i = 2; i <= N; i++)
      g << D[i] << " ";
   g << "\n";
   return 0;
}

void dijkstra(int pl) {
   for(int i = 1; i <= N; i++) {
      D[i] = INF, sel[i] = false;
   }
   D[pl] = 0;
   sel[pl] = true;

   for(auto i : G[pl]) {
      D[i.second] = i.first;
      Q.push(i);
   }

   while(!Q.empty()) {
      while(!Q.empty() && sel[Q.top().second])
         Q.pop();

      if(Q.empty()) break;

      int c = Q.top().first, y = Q.top().second;
      Q.pop();

      for(auto i : G[y])
         if(c + i.first < D[i.second]) {
            D[i.second] = c + i.first;
            Q.push({D[i.second], i.second});
         }
   }

}