#include <fstream>
#include <vector>
#include <set>
#define INF 1e9
#define N_MAX 50005
using namespace std;

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

vector<pair<int, int>> l[N_MAX];
set<pair<int, int>> s;
int n, m, d[N_MAX], x, y, c, k, vecin, cost;
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
  {
    cin >> x >> y >> c;
    l[x].push_back({y, c});
  }
  for (int i = 2; i <= n; i++)
    d[i] = INF;
  d[1] = 0;
  s.insert({0, 1});
  while (!s.empty())
  {
    k = s.begin()->second;
    s.erase(s.begin());
    for (int i = 0; i < l[k].size(); i++)
    {
      vecin = l[k][i].first;
      cost = l[k][i].second;
      if(d[vecin]>d[k]+cost)
      {
        s.erase({d[vecin],vecin});
        d[vecin]=d[k]+cost;
        s.insert({d[vecin],vecin});
      }
    }
  }
  for(int i=2;i<=n;i++)
  cout<<d[i]<<" ";
  
}