#include <bits/stdc++.h>
#define maxn 50000
#define maxm 250000
#define maxc 20000

using namespace std;

vector <int> g[maxn+5];
vector <int> cst[maxn+5];
bool viz[maxn+5];
unsigned int dst[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 );
    cst[a].push_back ( c );
  }

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

  pq.push ( 0 );
  int nod, nn;
  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];
        if ( viz[nn] == 0 && dst[nn] > dst[nod] + cst[nod][i] )
        {
          dst[nn] = dst[nod] + cst[nod][i];
          pq.push ( nn );
        }
      }
    }
  }

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

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

  return 0;
}