#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;
const int INF = 2000000000;

int N, M;
vector <int> Ad[NMAX];
vector <int> Cost[NMAX];
int dist[NMAX];
bool vis[NMAX];
priority_queue < pair<int,int>, vector<pair<int,int> >, greater<pair<int, int> > > pq;

void Read() {
    fin >> N >> M;
    for( int i = 1; i <= M; ++i ) {
        int a, b, d;

        fin >> a >> b >> d;
        Ad[a].push_back( b );
        Cost[a].push_back( d );
    }
}

void Do() {
    for( int i = 1; i <= N; ++i )
        dist[i] = INF;

    dist[1] = 0;

    pq.push( { 0, 1 } );

    while( !pq.empty() ) {
        int u, w;

        u = pq.top().second;
        pq.pop();

        if( vis[u] ) continue;
        else vis[u] = true;

        for( int i = 0; i < Ad[u].size(); ++i ) {
            w = Ad[u][i];

            if( dist[w] > dist[u] + Cost[u][i] ) {
                dist[w] = dist[u] + Cost[u][i];
                pq.push( { dist[w], w } );
            }
        }
    }

    for( int i = 2; i <= N; ++i )
        ( dist[i] == INF ) ? fout << "0 " : fout << dist[i] << ' ';

    fin.close();
    fout.close();
}

int main()
{
    Read();
    Do();

    return 0;
}