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

#define intPair pair<int, int>

using namespace std;

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

int n, e;
vector<pair<int, int>> v[50002];
int x, y, w;

void dijkstra(int src);

int main()
{
  cin >> n >> e;
  for(int i = 1; i <= e; i++)
  {
    cin >> x >> y >> w;
    v[x].push_back({y, w});
  }
  dijkstra(1);
  return 0;
}

void dijkstra(int src)
{
  vector<int> dist(n + 1, 1e9);
  priority_queue<intPair, vector<intPair>, greater<intPair>> pq;
  pq.push({0, src});
  dist[src] = 0;
  while(!pq.empty())
  {
    int crt_node = pq.top().second;
    pq.pop();
    for(auto link : v[crt_node])
    {
      int next_node = link.first;
      int weight = link.second;
      if(dist[next_node] > dist[crt_node] + weight)
      {
        dist[next_node] = dist[crt_node] + weight;
        pq.push({dist[next_node], next_node});
      }
    }
  }
  for(int i = 2; i <= n; i++)
    cout << dist[i] << ' ';
  cout << '\n';
  return ;
}