#include <iostream>
#include <fstream>
#define inf 100001

using namespace std;

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

int a[5000][5000], n, m;//date de intrare
// punctul de plecare este nodul 1

bool marcare[500001];//array in care se marcheaza nodurile prin care trecem
int distanta[500001];//array in care se pastreaza distanta de la nodul 1 la celelalte

void initializareDist(){
  for(int i = 1; i <= n; i++)
    if(a[1][i] != 0)
      distanta[i] = a[1][i];
    else
      distanta[i] = inf;
}

int cautValMin(){//functie care cauta nodul cu dist minima nemarcat, ca sa trec printr-un cost cat mai mic
  int minim = inf;
  int poz = -1;
  marcare[1] = true;
  for(int i = 1; i <= n; i++)
    if(distanta[i] < minim && marcare[i] == false){
      minim = distanta[i];
      poz = i;
    }
    return poz;
}

void rezolvare(){
  int plec = cautValMin();
  while(plec != -1){
    marcare[plec] = true;
    for(int i = 1; i <= n; i++)
      if(a[plec][i] != 0  && (distanta[i] ==  inf || distanta[i] > (a[plec][i] + distanta[plec])))
        distanta[i] = a[plec][i] + distanta[plec];
    plec = cautValMin();
  }
}

void citire(){
  in >> n >> m;
  for(int i = 1; i <= m; i++){
    int t1, t2, t3;
    in >> t1 >> t2 >> t3;
    a[t1][t2] = t3;
  }
  initializareDist();
}

void afisare(){
  for(int i = 2; i <= n; i++)
    if(distanta[i] != inf)
      out << distanta[i] << ' ';
    else
      out << '0' <<  ' ';
}

int main(){
  citire();
  rezolvare();
  afisare();
  return 0;
}