#include<fstream>
#include<queue>
#include<vector>
using namespace std;

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

#define DIM 250001
#define INF 0x3f3f3f3f

int n, m;

queue<int> Q;

vector<vector<pair<int, int> > > G;

int sol[DIM];

void Read();
void Dijkstra();
void Write();

int main()
{
    Read();
    Dijkstra();
    Write();
    
    fin.close();
    fout.close();
    
    return 0;
}

void Read()
{
     fin >> n >> m;
     G.resize(n+1);
     int x, y, c;
     sol[n] = INF;
     for( int i = 1; i <= m; ++i )
     {
          if( i < n )
              sol[i] = INF;
          fin >> x >> y >> c;
          G[x].push_back( make_pair( y, c ) );
          if(x == 1 )
               sol[y] = c;
     }
}

void Dijkstra()
{
     Q.push(1);
     sol[1] = 0;
     
     while( !Q.empty() )
     {
            int k = Q.front();
            for( int i = 0; i < G[k].size(); ++i )
            {
                 int j = G[k][i].first;
                 if( sol[j] > sol[k] + G[k][i].second )
                 {
                     Q.push(j);
                     sol[j] = sol[k] + G[k][i].second;
                 }
            }
            Q.pop();
     }
}

void Write()
{
     for( int i = 2; i <= n; ++i )
          fout << sol[i] << ' ';
     
     fout << '\n';
}