#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define DIM 50005
#define INF 2100000000

using namespace std;

ifstream fin  ("bellmanford.in");
ofstream fout ("bellmanford.out");

vector< pair< int, int > > v[DIM];
queue<int> q;
bitset<DIM> f;
int d[DIM], l[DIM];
int n, m, ii, jj, cc;
int nod, vecin, cost, ok;

void bellman_ford(int start){
    q.push(start);
    f[start]=1;

    while(!q.empty()){
        nod=q.front();
        f[nod] = 0;
        q.pop();

        for(int i=0; i < v[nod].size(); i++) {
            vecin=v[nod][i].first;
            cost =v[nod][i].second;
            if (d[vecin] > d[nod] + cost) {
                d[vecin] = d[nod] + cost;
                l[vecin]++;
                if(l[vecin] == n){
                    fout<<"Ciclu negativ!";
                    ok=1;
                    return;
                }

                if(f[vecin] == 0){
                    q.push(vecin);
                    f[vecin] = 1;
                }
            }
        }
    }
}

int main() {
    fin>>n>>m;
    while(m--){
        fin>>ii>>jj>>cc;
        v[ii].push_back( {jj, cc} );
    }

    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[1] = 0;

    bellman_ford(1);

    if(ok == 0)
        for(int i=2; i<=n; i++)
            fout<<d[i]<<" ";
    return 0;
}