#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iterator>
#define inf 1000001

using namespace std;

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

vector <pair <int, int > > vecini[50001];
vector <pair <int, int > > :: iterator it;
priority_queue < pair <int, int>, vector < pair <int, int> >, greater <pair <int, int> > > pq;
int dist [50001];
bool viz[50001];

void actualizareDist(int plec, int n){
  for(int i = 1; i <= n; i++){
    viz[i] = false;
    dist[i] = inf;
  }
  dist[plec] = 0;
}

void dijkstra(int plec,int n){
  actualizareDist(plec, n);
  pq.push({dist[plec], plec});
  while(!pq.empty()){
    int minim = pq.top().second;
    pq.pop();
    if(!viz[minim]){
      viz[minim] = true;
      for(it = vecini[minim].begin(); it !=vecini[minim].end(); it++)
        if(dist[it -> first] > dist[minim] + it -> second){
          dist[it -> first] = dist[minim] + it -> second;
          if(!viz[it -> first])
            pq.push({dist[it -> first], it -> first});

          }
    }
  }
}

void citire(){
  int t;//nr de matrice ce trebuie verificate
  int distanteDate[50001];
  //in >> t;
  for(int nr = 1; nr <= 1; nr++){
    int n, m, s;
    in >> n >> m ;//>> s;
    s = 1;
    // for(int i = 1; i <= n; i++)
    //   in >> distanteDate[i];
    for(int i = 1; i <= m; i++){
      int a, b, c;
      in >> a >> b >> c;
      vecini[a].push_back({b, c});
    }
    dijkstra(s,n);
    bool ok = true;
    for(int j = 1; j <= n; j++){
      if(dist[j] == inf)
        dist[j] = 0;
      out << dist[j] << ' ';
      // if(dist[j] != distanteDate[j]){
      //   ok = false;
      //   out <<"NU\n";
      //   break;
      // }
    }
    // if(ok == true)
    //   out << "DA\n";
    for(int i = 1; i <= n; i++)
      vecini[i].clear();
  }
}

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