#include<fstream>
#include<vector>
#include<queue>
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;
queue<int> Q;

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()
{
     Q.push(1);
     s[1] = true;
     
     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 )
                 {
                     sol[j] = sol[k] + G[k][i].second;
                     Q.push(j);
                 }
            }
            Q.pop();
     }
}

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