#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define maxn 50000
#define maxm 250000
#define inf INT_MAX/2-1

using namespace std;

vector <pii> g[maxn+5];
int dst[maxn+5];
bool viz[maxn+5];

struct compare
{
  bool operator () ( const int &a, const int &b )
  {
    return !(dst[a]<dst[b]);
  }
};

priority_queue <int,vector<int>,compare> PQ;

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

  int n, m; fin >> n >> m;

  int i, a, b, c;
  for ( i = 0; i < m; i++ )
  {
    fin >> a >> b >> c; a--; b--;
    g[a].push_back ( {b,c} );
  }

  for ( i = 1; i < n; i++ ) dst[i] = inf;

  int nod, nn;
  PQ.push ( 0 );
  while ( !PQ.empty() )
  {
    while ( !PQ.empty() && viz[PQ.top()] == 1 ) PQ.pop();
    if ( !PQ.empty() )
    {
      nod = PQ.top(); PQ.pop(); viz[nod] = 1;
      for ( i = 0; i < g[nod].size(); i++ )
      {
        nn = g[nod][i].fi;
        if ( viz[nn] == 0 && dst[nn] > dst[nod] + g[nod][i].se )
        {
          dst[nn] = dst[nod] + g[nod][i].se;
          PQ.push ( nn );
        }
      }
    }
  }

  for ( i = 1; i < n; i++ )
    if ( dst[i] == inf ) fout << "0 ";
    else fout << dst[i] << ' ';

  fin.close ();
  fout.close ();

  return 0;
}