// Dijkstra - O(MlogN)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#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;
bitset <Nmax> inPQ;

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;

              if(!inPQ[it->y]) {
                pq.push(it->y);
                inPQ[it->y] = 1;
              }
          }
  }

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