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

using namespace std;

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

struct elem{
  int b, c;
  elem * urm ;
}a[50001];

int  n, m;//date de intrare
// punctul de plecare este nodul 1

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

void initializareDist(){
  for(int i = 1; i <= n; i++)
    distanta[i] = inf;
  elem * parc = a[1].urm;
  while(parc != NULL){
    distanta[parc -> b] = parc -> c;
    parc = parc -> urm;
  }
}

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;
    elem * parc = a[plec].urm;
    while(parc != NULL){
      if(distanta[parc -> b] ==  inf || distanta[parc -> b] > (parc -> c + distanta[parc -> c]))
        distanta[parc -> b] = parc -> c + distanta[plec];
      parc = parc -> urm;
    }
    plec = cautValMin();
  }
}

void citire(){
  in >> n >> m;
  for(int i = 1; i <= n ;  i++)
    a[i].urm = NULL;
  for(int i = 1; i <= m; i++){
    int t1, t2, t3;
    in >> t1 >> t2 >> t3;
    elem * aux = new elem;
    aux -> urm = a[t1].urm;
    aux -> b = t2;
    aux -> c = t3;
    a[t1].urm  = aux;
  }
  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;
}