#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];

struct compare
{
  bool operator () ( const pii &a, const pii &b )
  {
    return a.se>b.se;
  }
};

priority_queue <pii,vector<pii>,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;
  pii yes;
  PQ.push ( {0,0} );
  while ( !PQ.empty() )
  {
    yes = PQ.top(); PQ.pop();
    nod = yes.fi;
    if ( yes.se == dst[nod] )
    {
      for ( i = 0; i < g[nod].size(); i++ )
      {
        nn = g[nod][i].fi;
        if ( dst[nn] > dst[nod] + g[nod][i].se )
        {
          dst[nn] = dst[nod] + g[nod][i].se;
          PQ.push ( {nn,dst[nn]} );
        }
      }
    }
  }

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

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

  return 0;
}