#include <bits/stdc++.h>

using namespace std;

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

class Compare
{
public:
  bool operator()(pair<int, int> p1, pair<int, int> p2)
  {
    return (p1.second > p2.second);
  }
};

const int NMAX = 50001, INF = 1 << 31 - 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
vector<pair<int, int>> lst[NMAX];
int cost[NMAX];

void Dij(int);

int main()
{
  int n, m;
  in >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cost[i] = INF;
  }

  for (int i = 0; i < m; i++)
  {
    int x, y, cost;
    in >> x >> y >> cost;
    lst[x].push_back(make_pair(y, cost));
  }

  Dij(1);

  for (int i = 2; i <= n; i++)
  {
    cout << cost[i] << ' ';
  }
  return 0;
}

void Dij(int s)
{
  pq.push(make_pair(s, 0));
  cost[s] = 0;

  while (!pq.empty())
  {
    auto curr = pq.top();
    pq.pop();
    int curr_node = curr.first;
    int curr_cost = curr.second;
    if (curr_cost <= cost[curr_node])
    {
      for (auto next : lst[curr_node])
      {
        int next_node = next.first;
        int edge_cost = next.second;
        if (curr_cost + edge_cost < cost[next_node])
        {
          cost[next_node] = curr_cost + edge_cost;
          pq.push(make_pair(next_node, cost[next_node]));
        }
      }
    }
  }
}