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

using namespace std;

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

int n, m, a, c, b;
int viz[50005];
bool marcat[50005];
vector <pair <int, int>> v[50005];
priority_queue <pair <int, int>> pq;
pair <int, int> p;

int main()	{
  fin >> n >> m;
  for (int i = 1; i <= m; ++i)	{
		fin >> a >> b >> c;
    v[a].push_back({c, b});
  }
  pq.push({0, 1});
  int nod, val;
  while (!pq.empty())	 {
		p = pq.top();
		pq.pop();
		swap(p.first, p.second);
		p.second = - p.second;
		if (viz[p.first] < p.second && marcat[p.first])
			continue;
//		cout << pq.size() << '\n';
    for (int i = 0; i < v[p.first].size(); ++i)	 {
      nod = v[p.first][i].second;
      val = v[p.first][i].first;
      if (marcat[nod] && viz[nod] <= val + p.second)
				continue;
      pq.push({ - val - p.second, nod});
			marcat[nod] = true;
			viz[nod] = val + p.second;
		}
  }
  for (int i = 2; i <= n; ++i)
		fout << viz[i] << ' ';
  return 0;
}