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

using namespace std;

#define MAXN 50000///
#define MAXM 250000///
#define INF 1000000001

struct node{
  int nod, cost;
  bool operator < (const node &other) const{
    if(cost > other.cost){///??
      return true;
    }else{
      return false;
    }
  }
};
vector <node> graph[MAXN];
priority_queue <node> pq;
int drum[MAXN];
bool frecv[MAXN];

void BFS(int startnode){
  int i, newnod;
  pq.push({startnode, 0});
  drum[startnode] = 0;
  while(!pq.empty()){
    newnod = pq.top().nod;
    pq.pop();
    if(frecv[newnod] == false){
      frecv[newnod] = true;
      for(i = 0; i < graph[newnod].size(); i++){
        if((drum[newnod] + graph[newnod][i].cost) < drum[graph[newnod][i].nod]){
          drum[graph[newnod][i].nod] = drum[newnod] + graph[newnod][i].cost;
          pq.push({graph[newnod][i].nod, drum[graph[newnod][i].nod]});
        }
      }
    }
  }
}

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