#include <fstream>
#include <queue>

using namespace std;

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

typedef pair<int, int> pii;

const int NMAX = 50002;
const int INF = 2000000000;

int N, M;
vector <int> Ad[NMAX];
vector <int> Cost[NMAX];

bool in_h[NMAX];
int d[NMAX];

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

   for( int i = 1; i <= M; ++i )
   {
     int a, b, d;

     fin >> a >> b >> d;

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

   fin.close();
}

void Do()
{
   priority_queue < pii, vector<pii>, greater<pii> > Heap;

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

   d[1] = 0;

   Heap.push( make_pair( 0, 1 ) );

   int nod;

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

     if( in_h[nod] ) continue;
     else in_h[nod] = true;

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

       if( d[nod] + Cost[nod][i] < d[w] )
       {
         d[w] = d[nod] + Cost[nod][i];
         Heap.push( make_pair( d[w], w ) );
       }
     }
   }

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

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

    return 0;
}