#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>

using namespace std;

#define MAXN 50000
#define MAXM 250000
#define INF (MAXN * 20000 + 1)

int best[MAXN];

struct nod{

  int node, cost;
  bool operator < (const nod &other) const{
      return cost > other.cost;
  }
};

priority_queue <nod> pq;
vector <nod>arb[MAXN];

void dijkstra(){
  int i, j;
  nod nodcoada;
  pq.push({0, 0});
  j = 0;
  while(0 < pq.size()){
    nodcoada = pq.top();
    pq.pop();
    if(best[nodcoada.node] == INF){
      best[nodcoada.node] = nodcoada.cost;
      for(i = 0; i < arb[nodcoada.node].size(); i++){
        if(best[arb[nodcoada.node][i].node] == INF){
          pq.push({arb[nodcoada.node][i].node, best[nodcoada.node] + arb[nodcoada.node][i].cost});
        }
      }
    }
  }
}

int main()
{
    FILE *fin, *fout;
    int n, m, a, b, i, cost;
    fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i = 0; i < m; i++){
      fscanf(fin, "%d%d%d", &a, &b, &cost);
      arb[a - 1].push_back({b - 1, cost});
    }
    fclose(fin);
    for(i = 0; i < n; i++){
      best[i] = INF;
    }
    dijkstra();
    fout = fopen("dijkstra.out", "w");
    for(i = 1; i < n; i++){
      if(best[i] == INF){
        fprintf(fout, "0 ");
      }else{
        fprintf(fout, "%d ", best[i]);
      }
    }
    fclose(fout);
    return 0;
}
/*struct nod{

  int node, cost;
  bool operator < (const nod &other) const{
      return cost > other.cost;
  }
};

priority_queue <nod> pq;
vector <nod>arb[MAXN];*/

/*struct nod{

  int node, cost;
  bool operator < (const nod &other) const{
      return cost > other.cost;
  }
};

priority_queue <nod> pq;
vector <nod>arb[MAXN];
    for(i = 1; i < n; i++){
      fscanf(fin, "%d", &a);
      if(a != best[i]){
        if((best[i] != INF) || (a != 0)){
          printf("EROARE %d %d ", best[i], a);
        }
      }*/