#include <iostream>
#include <fstream>
#include <utility>
#include <queue>
#include <functional>
#include <limits.h>

#define N_MAX 50000
#define M_MAX 250000

using namespace std;

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


class Node
{
public:
  int id;

  Node() {}
  Node(int id) : id(id) {}
};

int distances[N_MAX + 1];

bool compare(Node l, Node r)
{
  return distances[l.id] < distances[r.id];
}

bool visited[N_MAX + 1] = {0};
std::vector<pair<int, int>> adjacent[N_MAX + 1];
std::priority_queue<Node, vector<Node>, std::function<bool(Node, Node)>> node_q(compare);

void read(int &num_nodes, int &num_edges)
{
  int n1;
  int n2;
  int weight;

  fin >> num_nodes >> num_edges;
  for (int i = 0; i < num_edges; ++i)
  {
    fin >> n1 >> n2 >> weight;

    adjacent[n1].push_back(make_pair(n2, weight));
  }
}

void find_path(int source, int num_nodes)
{
  for (int i = 0; i < N_MAX + 1; ++i) {
    distances[i] = INT_MAX;
  }
  // Put initial node in queue, set distance to zero
  distances[source] = 0;
  node_q.push(Node(source));

  while (!node_q.empty()) {
    Node currentNode = node_q.top();
    node_q.pop();

    if (visited[currentNode.id]) {
      continue;
    }

    for (int i = 0; i < adjacent[currentNode.id].size(); ++i) {
      int nextNode = adjacent[currentNode.id][i].first;
      int edgeWeight = adjacent[currentNode.id][i].second;
      
      int potential_next_distance = distances[currentNode.id] + edgeWeight;

      if (potential_next_distance < distances[nextNode]) {
        distances[nextNode] = potential_next_distance;
      }

      node_q.push(Node(nextNode));
    }
    visited[currentNode.id] = true;
  }
}

void print(int num_nodes) {
  for (int i = 2; i <= num_nodes; ++i) {
    gout << distances[i] << " ";
  }
}

int main()
{
  int num_nodes;
  int num_edges;
  read(num_nodes, num_edges);
  cout << "Num nodes " << num_nodes << "\n";
  find_path(1, num_nodes);
  print(num_nodes);
}