#include <stdio.h>
#include <vector>
#include <set>

#define NMAXX 50000
#define INF 1000000000

using namespace std;

struct Edges {
    int node, cost;
};

int n, m, dist[NMAXX];
set<Edges> heap;
vector<Edges> graf[NMAXX];

bool operator<( const Edges& a, const Edges& b ) {
    if ( a.cost == b.cost )
        return a.node < b.node;

    return a.cost < b.cost;
}

void dijkstra(int node) {
    int i;
    Edges top;
    set<Edges>::iterator it;

    for ( i = 0; i < n; i++ )
        dist[i] = INF;

    heap.insert({node, 0});
    dist[node] = 0;
    while ( !heap.empty() ) {
        top = *heap.begin();
        heap.erase( heap.begin() );
        for ( Edges edge : graf[top.node] ) {
            if ( dist[edge.node] > edge.cost + top.cost ) {
                it = heap.find( {edge.node, dist[edge.node]} );
                if ( it != heap.end() )
                    heap.erase( it );

                dist[edge.node] = edge.cost + top.cost;
                heap.insert( {edge.node, edge.cost + top.cost} );
            }
        }
    }
}

int main() {
    FILE *fin, *fout;
    int i, x, y, z;

    fin = fopen( "dijkstra.in", "r" );
    fout = fopen( "dijkstra.out", "w" );

    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &x, &y, &z );

        graf[x - 1].push_back( { y - 1, z } );
    }

    dijkstra( 0 );

    for ( i = 1; i < n; i++ ) {
        if ( dist[i] != INF )
            fprintf( fout, "%d ", dist[i] );
        else
            fprintf( fout, "0 " );
    }

    fclose( fin );
    fclose( fout );
    return 0;
}