#include <iostream>
#include <fstream>
#include <set>
#include <iterator>

#define inf 1000001

using namespace std;

typedef pair <int , int > PII;
set <PII> a[500001];
set <PII> :: iterator it1, it2;

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

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;
}

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++){
      it2 = a[plec].upper_bound({i,0});
      int cost;
      if(it2 == a[plec].end() || it2 -> first != i)
        cost = -1;
      else
        cost = it2 -> second;
      if(cost != -1  && (distanta[i] ==  inf || distanta[i] > (cost + distanta[plec])))
        distanta[i] = cost + distanta[plec];
    }
    plec = cautValMin();
  }
}

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

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;
}