// Dijkstra - O(MlogN)
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50009
#define oo 2000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
 
struct edge{
  int y,c;
  edge(int y = 0, int c = 0) {
    this->y = y;
    this->c = c;
  }
};
 
 
int N, M, d[Nmax], ante[Nmax];
 
 
vector < edge > Graph[Nmax];
 
struct cmp
{ 
    bool operator()(const int &x,const int &y)const
    {   return d[x]>d[y];   };
};
priority_queue < int  , vector < int > , cmp > pq;
 
 
void Dijkstra(const int& S){
  /* init */
  for(int i =1; i <= N; ++i) {
    d[i] = ante[i] = oo;
  }
 
  d[S] = ante[S] = 0;
  for(pq.push(S); !pq.empty(); pq.pop() ){
      int node = pq.top();
 
      for(vector<edge>::iterator it = Graph[node].begin() ; it != Graph[node].end() ; ++it)
          if(d[node]+it->c < d[it->y]) {
              d[it->y] = d[node] + it->c;
              ante[it->y]=node;
              pq.push(it->y);
          }
  }
 
  /* ATENTIE */
  for (int i = 1; i <= N; ++i)
      if (d[i] == oo) d[i] = ante[i] = 0;
}
 
 
void Rebuild(const int& node, const int& S) {
    if(node == S) { 
      g<<S<<' '; 
      return; 
    }
     
    Rebuild(ante[node], S);
     
    g<<node<<' ';
}
 
 
 
int main(){
  int S, F;
  f >> N >> M; 
  S = 1; 
  F = N;
 
  for(int i = 1; i <= M; ++i) {
    int x, y, c;
    f >> x >> y >> c;
     
    Graph[x].push_back(edge(y, c));
     
    /* daca graful e neorientat  */
 
    //Graph[y].push_back(edge(x, c));
 
  }
 
  //Fa drumurile de la S la toate celelalte noduri
  Dijkstra(S);
  for (int i = 2; i <= N; i++) {
    g << d[i] << ' ';
  }
  g << '\n';
 
  /*
  g << "Drumul de la "<< S<< " la " << F << " are lungimea "<< d[F] <<"\n";       
  g << "si este:\n";
  Rebuild(F, S); // Afiseaza drumul minim S-...-F
  g << '\n';
  */
  f.close();g.close();
  return 0;
}