#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[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++)
    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;
}

int cautareElem(int nod,int caut){
  elem * parc = a[nod].urm;
  while(parc != NULL){
    if(parc -> b == caut)
      return parc -> c;
    parc = parc -> urm;
  }
  return -1;
}

void rezolvare(){
  int plec = cautValMin();
  while(plec != -1){
    marcare[plec] = true;
    for(int i = 1; i <= n; i++){
      int cost = cautareElem(plec, i);
      if(cost != -1  && (distanta[i] ==  inf || distanta[i] > (cost + distanta[plec])))
        distanta[i] = cost + distanta[plec];
    }
    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;
}