#include <bits/stdc++.h>
#define DIM 100001

using namespace std;

ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");

vector < pair < int, int> > G[DIM];

int dp[DIM], inQ[DIM], relaxed[DIM];

int n, m, x, y, z;

void Bellman(){

    fill(dp + 1, dp + n + 1, 1e9);

    dp[1] = 0;

    inQ[1] = 1;

    relaxed[1] = 1;

    queue <int> Q;

    Q.push(1);

    while(!Q.empty()){

        int node = Q.front();

        inQ[node] = 0;

        Q.pop();

        for(auto k : G[node])

            if(dp[k.first] > dp[node] + k.second){

                dp[k.first] = dp[node] + k.second;

                if(!inQ[k.first]){

                    inQ[k.first] = 1;

                    relaxed[k.first]++;

                    if(relaxed[k.first] >= n){

                        fout << "Ciclu negativ!";

                        exit(0);

                    }

                    Q.push(k.first);


                }

            }

    }

    for(int i=2;i<=n;i++)

        fout << dp[i] << " ";

}

int main(){

    fin >> n >> m;

    while(m--){

        fin >> x >> y >> z;

        G[x].push_back({y, z});

    }

    Bellman();

}