#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>

#define N_MAX 50001
#define INF -1

using namespace std;

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

struct edge
{
  int node, cost;
};

struct nodeCost
{
  int node, cost;
  bool operator<(const nodeCost &e) const
  {
    return cost < e.cost || (cost == e.cost && node > e.node);
  }
};

int n, m, a, b, v;
vector<edge> graph[N_MAX];

vector<int> calculateCosts()
{
  set<nodeCost> costs;
  vector<int> finalCosts(n, INF);

  costs.insert({0, 0});

  while (costs.size() > 0)
  {
    auto first = *(costs.begin());
    costs.erase(costs.begin());

    finalCosts[first.node] = first.cost;

    for (auto d : graph[first.node])
    {
      int lungNou = first.cost + d.cost;
      if (finalCosts[d.node] > lungNou || finalCosts[d.node] == INF)
      {
        costs.erase({d.node, finalCosts[d.node]});
        costs.insert({d.node, lungNou});
        finalCosts[d.node] = lungNou;
      }
    }
  }

  return finalCosts;
}

int main()
{
  in >> n >> m;
  for (int i = 0; i < m; i++)
  {
    in >> a >> b >> v;
    graph[a - 1].push_back({b - 1, v});
  }

  auto aa = calculateCosts();

  for (int i = 1; i < aa.size(); i++)
  {
    if (aa[i] != INF)
    {
      out << aa[i] << ' ';
    }
    else
    {
      out << "0 ";
    }
  }

  return 0;
}