#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");

//Graf dens -> matrice de adiacență - cost[][]
//const int MAX_N = 1000;
//const int MAX_M = (MAX_N * (MAX_N + 1)) / 2;


//Graf rar -> liste de adiacență - vector<int>
const int MAX_N = 50000;
const int MAX_M = 500000;


const int INF = 0x7fffffff;
int N, M, u, v, c;

struct Muchie {
  int vecin;
  int cost;
};


struct Nod {
  int nod;
  int cost;


  bool operator < (const Nod &other) const {
    return this->cost > other.cost;
  }
};
vector<Muchie> vecini[1 + MAX_N];
bool vizitat[1 + MAX_N];
int cost[1 + MAX_N]; // adancime (in DFS si BFS)
int tata[1 + MAX_N]; // deUnde (pentru Dijkstra)
int main() {
  fscanf(fin, "%d%d", &N, &M);
  for (int i = 1; i <= M; i++) {
    fscanf(fin, "%d%d%d", &u, &v, &c);
    vecini[u].push_back({v, c});
  }
  int start = 1;
  // Dijkstra
  priority_queue<Nod> frontiera;
  for(int i = 1; i <= N; i++) {
    cost[i] = INF;
  }
  cost[1]=0;
  frontiera.push({start, 0});
  while (!frontiera.empty()) {
    int nod = frontiera.top().nod;
    frontiera.pop();
    if (!vizitat[nod]) {
      vizitat[nod] = true;
      for (Muchie m : vecini[nod]) {
        if (cost[m.vecin] > cost[nod] + m.cost) {
            cost[m.vecin] = cost[nod] + m.cost;
            frontiera.push({m.vecin, cost[m.vecin]});
        }
      }
    }
  }
  for(int i=2;i<=N;i++)
  {
      if(vizitat[i]==false) fprintf(fout, "0 ");
      else fprintf(fout,"%d ", cost[i]);
  }
  return 0;
}