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

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

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

vector<pair<int, int> > G[Nmax];
char viz[Nmax];
int dist[Nmax];

int main()
{
  ifstream f ("dijkstra.in");
  ofstream g ("dijkstra.out");
  
  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));
  }
  
  priority_queue<pii, vector<pii>, greater<pii> > Q;
  memset(viz, 0, sizeof(viz));
  memset(dist, -1, sizeof(dist));
  
  Q.push(make_pair(0,0));
  while(!Q.empty()) {
    pii P = Q.top();
    Q.pop();
    int d = P.first;
    int a = P.second;
    if (viz[a])
      continue;
    viz[a] = 1;
    dist[a] = d;
    for (auto X: G[a]) {
      int x = X.first;
      int dx = X.second;
      if (viz[x])
        continue;
      if (dist[x] == -1 || dist[x] > dx + dist[a]) {
        dist[x] = dx + dist[a];
        Q.push(make_pair(dist[x], x));
      }
    }
  }
  
  for (int a = 1; a < N; a++)
    g << (dist[a] == -1 ? 0 : dist[a]) << (a == (N-1) ? '\n' : ' ');
  
  return 0;
}