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

using namespace std;

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

int n, m, a, b, c, inf = 2e9, d[50001];
vector < pair <int, int> > v[50001];
priority_queue < int > q;
bool ve[50001];

void dijkstra (int nodc) {
  int nodv, cost;
  for (int i = 1; i <= n; i++)
    d[i] = inf;
  ve[nodc] = true; d[nodc] = 0;
  q.push (nodc);
  while (not q.empty ()) {
    nodc = q.top ();
    q.pop ();
    for (int i = 0; i < v[nodc].size (); i++) {
      nodv = v[nodc][i].first; cost = -v[nodc][i].second;
      if (d[nodv] > d[nodc] + cost) {
        d[nodv] = d[nodc] + cost;
        ve[nodv] = true;
        q.push (nodv);
      }
    }
  }
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> a >> b >> c;
    v[a].push_back ({b, -c});
  }
  dijkstra (1);
  for (int i = 2; i <= n; i++)
    if (d[i] != inf)
      fout << d[i] << ' ';
    else
      fout << "0 ";
  return 0;
}