#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
using namespace std;

#define Nmax 50002
#define inf 0x3f3f3f3f

FILE *f = fopen ( "bellmanford.in", "r" );
FILE *g = fopen ( "bellmanford.out", "w" );

vector < pair < int, int > > G[Nmax];
bitset < Nmax > inQ;
queue < int > Q;
int dist[Nmax], ap[Nmax], N, M;
bool cycle;

void Bellman_Ford ( int start ){

   vector < pair < int, int > > :: iterator it;

   Q.push ( start );
   inQ[start] = 1;
   ap[start] = 1;

   while ( !Q.empty() ){
        int nod = Q.front();
        Q.pop();

        for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
            int now = it -> first;
            if ( dist[now] > dist[nod] + it -> second ){
                dist[now] = dist[nod] + it -> second;
                if ( !inQ[now] ){
                    Q.push ( now );
                    inQ[now] = 1;
                    ap[now]++;
                    if ( ap[now] >= N ){
                        fprintf ( g, "Ciclu negativ!" );
                        cycle = 1;
                        return;
                    }
                }
            }
        }
   }
}


int main(){

    int x, y, c, Start = 1;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 2; i <= N; ++i )
        dist[i] = inf;

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d%d", &x, &y, &c );
        G[x].push_back ( make_pair ( y, c ) );
    }

    Bellman_Ford ( Start );

    if ( !cycle )
        for ( int i = 2; i <= N; ++i )
           fprintf ( g, "%d ", dist[i] );

    return 0;
}