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

using namespace std;

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

const int NMAX = 5 * 1e4;
const int INF = 1 << 30;

struct Edge {
  int node;
  int cost;

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

int n, m;
int dist[1 + NMAX];

vector < Edge > g[1 + NMAX];

priority_queue < Edge > pq;

void dijkstra() {
  for(int i = 1; i <= n; i++)
    dist[i] = INF;

  dist[1] = 0;
  pq.push({1, 0});

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

    if(from.cost != dist[from.node])
      continue;

    for(int i = 0; i < g[from.node].size(); i++) {
      Edge to = g[from.node][i];
      to.cost += from.cost;

      if(to.cost < dist[to.node]) {
        dist[to.node] = to.cost;
        pq.push(to);
      }
    }
  }
}

int main()
{
  in >> n >> m;

  for(int i = 1; i <= m; i++) {
    int from, to, cost;

    in >> from >> to >> cost;

    g[from].push_back({to, cost});
  }

  dijkstra();

  for(int i = 2; i <= n; i++) {
    if(dist[i] == INF)
      out << "0 ";
    else
      out << dist[i] << ' ';
  }

  out << '\n';

  in.close();
  out.close();

  return 0;
}