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

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMAX = 50000;
const int inf = 1 << 30;

struct Edge{
  int to;
  int dist;
};

struct Data {
  int node;
  int cost;

  bool operator< (Data other) const {
    return cost < other.cost;
  }
};

int n, m;
int dist[1 + NMAX];
vector < Edge > g[1 + NMAX];
priority_queue < Data > pq;

void read() {
  in >> n >> m;
  for(int i = 1; i <= m; i++) {
    int from, to, cost;
    in >> from >> to >> cost;
    g[from].push_back({to, cost});
  }
}

void init() {
  for(int i = 2; i <= n; i++)
    dist[i] = inf;

  dist[1] = 0;
}

void dijkstra() {
  pq.push({1, 0});

  while(!pq.empty()) {
    Data from = pq.top();
    pq.pop();

    for(int i = 0; i < g[from.node].size(); i++) {
      Data to;
      to.node = g[from.node][i].to;
      to.cost = g[from.node][i].dist + from.cost;
      if(to.cost < dist[to.node]) {
        dist[to.node] = to.cost;
        pq.push(to);
      }
    }
  }
}

void write() {
  for(int i = 2; i <= n; i++)
    out << dist[i] << ' ';
  out << '\n';
}

int main()
{
  read();
  init();
  dijkstra();
  write();

  in.close();
  out.close();
  return 0;
}