#include <bits/stdc++.h>
#define dim 50009
#define inf 1e9 + 1
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, x, y, cost;
vector< vector< pair< int, int > > > v(dim);
vector<bool> inCoada(dim);
queue<int> coada;
vector<int> d(dim, inf), coadaCnt(dim, 0);

int main() {

    fin >> n >> m;

    for(int i = 0; i < m; i++) {
        fin >> x >> y >> cost;
        v[x].push_back( make_pair(y, cost));
    }
    coada.push(1);
    inCoada[1] = true;
    coadaCnt[1] = 1;
    d[1] = 0;


    while( !coada.empty() ) {
        int nod = coada.front();
        coada.pop();
        inCoada[nod] = false;

        for(int j = 0; j < v[nod].size(); j++) {
            if( d[ v[ nod ][j].first ] > d[ nod ] + v[ nod ][j].second  ) {
                    d[ v[ nod ][j].first ] = d[ nod ] + v[ nod ][j].second;
                    if( !inCoada[ v[nod][j].first ] ) {
                         if( coadaCnt[ v[nod][j].first ] > n ) {
                            fout << "Ciclu negativ!";
                            return 0;
                         } else {
                            coada.push( v[nod][j].first );
                            coadaCnt[ v[nod][j].first ]++;
                            inCoada[ v[nod][j].first ] = true;
                         }
                    }
                }
        }
    }

        for(int i = 2; i <= n; i++) 
            fout << d[i] << " ";
        

    return 0;
}