using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "dijkstra";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 50e3;
struct Nod {
   int nod; unsigned cost;
   bool operator<(const Nod &B) const
   { return cost > B.cost; }
};

int n, m;
unsigned d[nMAX + 1];
vector<pair<int, int>> gf[nMAX + 1];

int main()
{
   cin >> n >> m;
   for (int i = 1; i <= m; ++i)
   {
      int a, b, c;
      cin >> a >> b >> c;
      gf[a].pb(mp(b, c));
   }

   priority_queue<Nod> pq;
   fill(d + 1, d + n+1, INT_MAX);
   d[1] = 0;
   pq.push({1, 0});

   while (!pq.empty())
   {
      auto [nod, cost] = pq.top();
      pq.pop();

      if (cost > d[nod])
         continue;

      for (auto nex : gf[nod])
         if (cost + nex.se < d[nex.fi])
         {
            d[nex.fi] = cost + nex.se;
            pq.push({nex.fi, d[nex.fi]});
         }
   }

   for (int i = 2; i <= n; ++i)
      if (d[i] == INT_MAX)
         d[i] = 0;

   for (int i = 2; i <= n; ++i)
      cout << d[i] << ' ';
}