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

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

#define DIM 50002
#define INF 0x3f3f3f3f

int n, m;

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

bool s[DIM];
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 a, b, c;
     for( int i = 1; i <= m; ++i )
     {
          fin >> a >> b >> c;
          G[a].push_back( make_pair( b, c ) );
     }
     
     for( int i = 2; i <= n; ++i )
          sol[i] = INF;  
}

void Dijkstra()
{
     sol[1] = 0;
     s[1] = true;
     
     for( int i = 0; i < G[1].size(); ++i )
          sol[ G[1][i].first ] = G[1][i].second;
     
     int minim = INF;
     int k;
     
     for( int p = 1; p <= n - 1; ++p )
     {
          minim = INF;
          for( int i = 2; i <= n; ++i )
               if( !s[i] && sol[i] < minim )
               {
                   minim = sol[i];
                   k = i;
               }
          
          s[k] = true;
          
          for( int i = 0; i < G[k].size(); ++i )
               if( !s[ G[k][i].first ] && sol[ G[k][i].first ] > sol[k] + G[k][i].second )
                   sol[ G[k][i].first ] = sol[k] + G[k][i].second;
     }
     
}

void Write()
{
     for( int i = 2; i <= n; ++i )
          if( sol[i] != INF )
              fout << sol[i] << ' ';
          else
              fout << 0 << ' '; 
}