#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], frecv[MAXN];

vector <int>costuri[MAXN];
vector <int>arb[MAXN];

struct cmp {
    bool operator() (int a, int b) const {
        return -best[a] < -best[b];
    }
};

std::priority_queue <int, std::vector <int>, cmp> pq;

void dijkstra(){
  int i, nodcoada;
  pq.push(0);
  best[0] = 0;
  while(0 < pq.size()){
    nodcoada = pq.top();
    pq.pop();
    if(frecv[nodcoada] == 0){
      frecv[nodcoada] = 1;
      for(i = 0; i < arb[nodcoada].size(); i++){
        if((best[nodcoada] + costuri[nodcoada][i]) < best[arb[nodcoada][i]]){
          best[arb[nodcoada][i]] = best[nodcoada] + costuri[nodcoada][i];
          pq.push(arb[nodcoada][i]);
        }
      }
    }
  }
}

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);
      costuri[a - 1].push_back(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, "%d ", best[i]);
      }else{
        fprintf(fout, "0 ");
      }
    }
    fclose(fout);
    return 0;
}