#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50009
#define INF 9999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


/*
G[x]: (y, c) // am muchie x->y de cost c

*/
typedef pair<int,int> edge;
#define first y
#define second c

int N, M, d[Nmax], ante[Nmax];


vector < edge > Graph[Nmax];


/*
priority_queue <=> heap
bag elemente (noduri) in elemente
1, 5, 10
si vreau sa le ordoneze dupa distanta fata de sursa (in varf sa fie minim)
d[1], d[5], d[10]
3     4     1
in varf va fi 10

*/
struct cmp
{
	// d[x] = 10, d[y] = 2 => return true => interschimba-le
	// false => daca x si y sunt deja ordonate (y este mai aproape de varf decat x)
    bool operator()(int x, int y)
    {
		return d[x] > d[y];
	};
};
priority_queue < int  , vector < int > , cmp > pq;

/*
	Dijkstra  e ca un BFS


	BFS - lungime
				1
			  1	S 1 2
			    1 2
			    2

	Dijkstra - costul muchiei


			S  - x (se duce la cel mai apropiat vecin dupa cost)

*/
void Dijkstra(const int& S){
  /* init */
  for(int i =1; i <= N; ++i) {
    d[i] = parent[i] = INF;
  }

  pq.push(S);
  d[S] = 0;
  parent[S] = 0;

  while (!pq.empty()){
      // ia si sterge elementul din varf
	  int node = pq.top();
	  pq.pop();

      for(auto it : G[node])
          if(d[node]+it.c < d[it.y]) {
              d[it.y] = d[node] + it.c;
              parent[it.y]=node;

              pq.push(it.y);
          }
  }

}


void Rebuild(const int& node, const int& S) {
    if(node == S) {
      g<<S<<' ';
      return;
    }

    Rebuild(parent[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, d, parent);
  /* ATENTIE */
  for (int i = 1; i <= N; ++i)
      if (d[i] == INF) d[i] = parent[i] = 0;

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