#include<fstream> 
#include<vector> 
#include<queue> 
#define pb push_back
#define DIM 50003
#define INF 0x3f3f3f3f
using namespace std; 

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

int N, M, Dist[DIM];
vector< pair< int, int > > G[DIM];
queue< int > Q;
bool viz[DIM];

void Solve(){
    viz[1] = 1;
    Q.push(1);
    while( !Q.empty() )
    {
        int x = Q.front();
        Q.pop(); 
        viz[x] = 0;
        for(vector< pair< int, int > > ::iterator it = G[x].begin(); it != G[x].end(); ++it )
            if( Dist[x] + it -> second < Dist[it -> first] ) {
                Dist[it -> first] = Dist[x] + it -> second;
            if( !viz[it -> first] )
                viz[it -> first] = 1, Q.push(it -> first);
            }
    }
}
int main()
{
    int i, x, y, c;
    in >> N >> M;
    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        G[x].pb(make_pair(y,c));
    }
    for(i = 2; i <= N; i++)
        Dist[i] = INF;
    Solve();
    
    for(i = 2; i <= N; i++)
        out << Dist[i] << " "; 
    return 0;
}