#include <stdio.h>
#include <vector>
#include <queue>
    
static inline int max( int a, int b ) {
    return ( a >= b ? a : b );
}
 
static inline int min( int a, int b ) {
    return ( a <= b ? a : b );
}

FILE *fin;
int poz, val;
char buff[ ( 1 << 7 ) ];
char nextChar() {
    if( poz == sizeof( buff ) ) {
        fread( buff, 1, sizeof( buff ), fin );
        poz = 0;
    }

    return buff[ poz++ ];
}

bool f[ 100 ];
int readInt() {
    int rez = 0, ch;
    while( !f[ ch = nextChar() ] );
    do
        rez = rez * 10 + ch - '0';
    while( f[ ch = nextChar() ] );
    return rez;
}

#define MAX 50001
std::vector<std::pair<int, int>> v[ MAX ];
long long dp[ MAX ];
bool ok[ MAX ];
int n, k;

std::queue<int> q;
void Lee() {
    dp[ 1 ] = 0;
    ok[ 1 ] = 1;
    q.push( 1 );
    while( !q.empty() ) {
        int poz = q.front();
        q.pop();

        for( int i = 0; i < v[ poz ].size(); i++ )
            if( !ok[ v[ poz ][ i ].first ] || ( dp[ v[ poz ][ i ].first ] > dp[ poz ] + v[ poz ][ i ].second ) ) {
                dp[ v[ poz ][ i ].first ] = dp[ poz ] + v[ poz ][ i ].second;
                ok[ v[ poz ][ i ].first ] = 1;
                q.push( v[ poz ][ i ].first );
            }
    }   
}

int main()
{
    val = sizeof( buff );
    
    f[ '1' ] = f[ '2' ] = f[ '3' ] = f[ '4' ] = f[ '5' ] = 1;
    f[ '6' ] = f[ '7' ] = f[ '8' ] = f[ '9' ] = f[ '0' ] = 1;
 
    fin = fopen( "dijkstra.in", "r" );
    fread( buff, 1, sizeof( buff ), fin );
    n = readInt();
    k = readInt();
    for( int i = 0; i < k; i++ )
        v[ readInt() ].push_back( { readInt(), readInt() } );
    fclose( fin );

    Lee();

    FILE *fout = fopen( "dijkstra.out", "w" );
    for( int i = 2; i <= n; i++ )
        fprintf( fout, "%lld ", dp[ i ] );
    fclose( fout );
    return 0;
}