#include <stdio.h>
    
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 );
}

struct pp{
    int first, second;
};
 
FILE *fin;
int poz, val;
char buff[ ( 1 << 10 ) ];
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, semn = 1;
    while( !f[ ch = nextChar() ] );
    if( ch == '-' ) {
        semn = -1;
        ch = nextChar();
    }

    do
        rez = rez * 10 + ch - '0';
    while( f[ ch = nextChar() ] );
    
    return rez * semn;
}
 
#include <bitset>
#include <vector>
#include <queue>

#define MAX 50001
std::vector<pp> v[ MAX ];
std::bitset<MAX> in;
long long dp[ MAX ];
int freq[ MAX ];
int n, k;
 
std::queue<int> q;
bool Lee() {
    for( int i = 0; i <= n; i++ )
        dp[ i ] = 1e9;

    dp[ 1 ] = 0;
    in[ 1 ] = 1;
    q.push( 1 );
    while( !q.empty() ) {
        int poz = q.front();
        in[ poz ] = 0;
        q.pop();
 
        for( int i = 0; i < v[ poz ].size(); i++ )
            if( ( dp[ v[ poz ][ i ].first ] > dp[ poz ] + v[ poz ][ i ].second ) ) {
                dp[ v[ poz ][ i ].first ] = dp[ poz ] + v[ poz ][ i ].second;
                if( ++freq[ v[ poz ][ i ].first ] == n )
                    return false;
                if( !in[ v[ poz ][ i ].first ] ) {
                    q.push( v[ poz ][ i ].first );
                    in[ v[ poz ][ i ].first ] = 1;
                }
            }
    }
    return true;   
}
 
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' ] = f[ '-' ] = 1;
    ////////////////////////////////////

    fin = fopen( "bellmanford.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( "bellmanford.out", "w" );
    if( !Lee() )
        fprintf( fout, "Ciclu negativ!\n" );
    else for( int i = 2; i <= n; i++ )
        fprintf( fout, "%lld ", dp[ i ] );
    fclose( fout );
    return 0;
}