#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;
const int Nmax = 50333;

vector<pii> G[Nmax];
char inQueue[Nmax];
int dist[Nmax];


int main()
{
  ifstream f ("dijkstra.in");
  ofstream g ("dijkstra.out");
 
  memset(inQueue, 0, sizeof(inQueue));
  memset(dist, 0x3f, sizeof(dist));
  
  int N, M, a, b, d;
  f >> N >> M;
  for (int i = 0; i < M; i++) {
    f >> a >> b >> d;
    a--;
    b--;
    G[a].push_back(make_pair(b,d));
  }
  
  queue<int> Q;
  dist[0] = 0;
  Q.push(0);
  inQueue[0] = 1;

  while(!Q.empty()) {
    int a = Q.front();
    Q.pop();
    inQueue[a] = 0;
    
    for (auto P: G[a]) {
      if (dist[P.first] > dist[a] + P.second) {
        dist[P.first] = dist[a] + P.second;
        if (!inQueue[P.first]) {
          Q.push(P.first);
          inQueue[P.first] = 1;
        }
      }
    }
  }
  
  for (int a = 1; a < N; a++)
    g << (dist[a] == INF ? 0 : dist[a]) << (a < N-1 ? ' ' : '\n');
  return 0;
}