/// bellman ford
#include <fstream>
#include <vector>
#define maxn 50000
#define inf 2147483600

using namespace std;

vector <int> v[maxn+5]; /// drumuri
vector <int> len[maxn+5]; /// lungime drum
int sz[maxn+5];
int cost[maxn+5]; /// cost de la 1 la 2..n

vector <int> qu;

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

  int n, m; /// noduri arce

  fin >> n >> m;

  int i, a, b, val;

  for ( i = 0; i < m; i++ )
  {
    fin >> a >> b >> val;
    a--; b--;
    v[a].push_back ( b );
    len[a].push_back ( val );
    sz[a]++;
  }

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

  int st = 0, dr = 0, cur, nod;
  qu.push_back ( 0 );
  while ( st <= dr )
  {
    nod = qu[st];
    for ( i = 0; i < sz[nod]; i++ )
      if ( cost[nod] + len[nod][i] < cost[v[nod][i]] )
      {
        dr++;
        cost[v[nod][i]] = cost[nod] + len[nod][i];
        qu.push_back ( v[nod][i] );
      }
    st++;
  }

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

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

  return 0;
}