#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int INF = ( 1 << 30 );
const int NMAX = 50005;

int N, M;

typedef pair < int, int > Pair;

int d[NMAX];

vector <int> Ad[NMAX];
vector <int> Cost[NMAX];

bool in_h[NMAX];

void Read()
{
  fin >> N >> M;

  int a, b, d;

  while( fin >> a >> b >> d )
  {
    ++M;

    Ad[a].push_back(b);
    Cost[a].push_back(d);
  }

  fin.close();
}

void Do()
{
  for( int i = 1; i <= N; ++i )
   d[i] = INF;

  d[1] = 0;

  priority_queue < Pair, vector<Pair>, greater<Pair> > H;

  H.push( make_pair( 0, 1) );
  in_h[1] = true;

  int nod, w;

  while( !H.empty() )
  {
    nod = H.top().second;
    H.pop();

    in_h[nod] = false;

    for( int i = 0; i < Ad[nod].size(); ++i )
    {
      w = Ad[nod][i];

      if( d[w] > d[nod] + Cost[nod][i] && !in_h[w] )
      {
        d[w] = d[nod] + Cost[nod][i];

        H.push( make_pair( d[w], w ) );
        in_h[w] = true;
      }
    }
  }
}

void Print()
{
  for( int i = 2; i <= N; ++i )
    if( d[i] == INF ) fout << "0 ";
    else fout << d[i] << ' ';

  fout.close();
}

int main()
{
    Read();
    Do();
    Print();

    return 0;
}