#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 InQueue[DIM];

void Solve()
{
    Dist[1] = 0;
    Q.push(1);
    InQueue[1] = true;
    while( !Q.empty() )
    {
        int x = Q.front();
        Q.pop(); 
        InQueue[x] = false;
        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( InQueue[it -> first] == 0 )
                InQueue[it -> first] = true, 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 = 1; i <= N; i++)
        Dist[i] = INF;
    Solve();
    
    for(i = 2; i <= N; i++)
        if( Dist[i] < INF )
            out << Dist[i] << " ";
        else out << "0 " ;
    return 0;
}