#include <bits/stdc++.h>
#include <iterator>

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

map<int, set<int>> M;
map<pair<int, int>, int> Cost_muchie;
int n;
vector<bool>Used;

vector<int> Cost_nod;
int minim(vector<int> v)
{
  int mini = INT_MAX, nod = -1, i;

  for (i = 1; i <= n; i++)
    if (!Used[i] && v[i] < mini)
    {
      mini = v[i];
      nod = i;
    }

  return nod;
}

void Dijkstra(int first)
{
  Cost_nod.resize(n + 10, INT_MAX);
  Used.resize(n + 10,false);
  
  Cost_nod[first] = 0;
  int i;

  for (i = 1; i <= n; i++)
  {
    int node = minim(Cost_nod);

    if (node != -1)
    {
      Used[node] = 1;

      for (auto it : M[node])
        if (Cost_nod[node] + Cost_muchie[{node, it}] < Cost_nod[it])
          Cost_nod[it] = Cost_nod[node] + Cost_muchie[{node, it}];
    }
  }
}

int main()
{
  int m, x, y, cost;
  fin >> n >> m;

  for (int i = 1; i <= m; i++)
  {
    fin >> x >> y >> cost;
    M[x].insert(y);
    Cost_muchie[{x, y}] = cost;
  }

  Dijkstra(1);

  int i;
  for (i = 2; i <= n; i++)
  {
    if (Cost_nod[i] == INT_MAX)
      fout << -1 << ' ';
    else
      fout << Cost_nod[i] << ' ';
  }

  return 0;
}