#include <iostream>
#include <vector>
#include <queue>

#define MAXN 50010
#define INF 1000000000000
using namespace std;

struct edge{
  long long cost;
  int pos;
};

struct node{
  long long dist;
  bool vis;
  vector <edge> neighbours;
};

struct auxInfo{
  int pos;
  long long dist;
};

bool operator<(auxInfo a, auxInfo b) {
  return a.dist > b.dist;
}

node graph[MAXN];
priority_queue <auxInfo> pq;

void dfs() {
  int i, pos;

  for ( i = 0; i < MAXN; i++ ) {
    graph[i].dist = INF;
  }

  graph[1].dist = 0;

  pq.push({1, 0});

  while ( pq.size() ) {
    pos = pq.top().pos;
    pq.pop();

    if ( !graph[pos].vis ) {
      graph[pos].vis = true;
      for ( edge v : graph[pos].neighbours ) {
        if ( graph[v.pos].dist > graph[pos].dist + v.cost ) {
          graph[v.pos].dist = graph[pos].dist + v.cost;
          pq.push({v.pos, graph[v.pos].dist});
        }
      }
    }
  }
}

void addEdge(int a, int b, long long cost) {
  graph[a].neighbours.push_back({cost, b});
}

int main() {
  FILE *fin, *fout;
  fin = fopen("dijkstra.in", "r");
  fout = fopen("dijkstra.out", "w");

  int n, m, i, a, b, c;

  fscanf(fin, "%d%d", &n, &m);

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d%d", &a, &b, &c);

    addEdge(a, b, c);
  }

  dfs();

  for ( i = 2; i <= n; i++ ) {
    if ( graph[i].dist == INF ) {
      graph[i].dist = 0;
    }
    fprintf(fout, "%lld ", graph[i].dist);
  }
  fprintf(fout, "\n");

  fclose(fin);
  fclose(fout);

  return 0;
}