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

using namespace std;

ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");

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

int n, m, i, x, y, cost;

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

bool ok;

queue <int> Q;

int main(){

    fin >> n >> m;

    for(i=1;i<=m;i++){

        fin >> x >> y >> cost;

        G[x].push_back(make_pair(y, cost));

    }

    for(i=1;i<=n;i++)

        dp[i] = 1e9;

    Q.push(1);

    inQ[1] = 1;

    dp[1] = 0;

    wasinQ[1] = 1;

    ok = true;

    while(!Q.empty() && ok){

        int node = Q.front();

        Q.pop();

        inQ[node] = 0;

        for(auto k : G[node])

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

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

                if(!inQ[k.first]){

                    wasinQ[k.first]++;

                    if(wasinQ[k.first] == n)

                        ok = false;

                    else {

                        wasinQ[k.first]++;

                        inQ[k.first] = 1;

                        Q.push(k.first);

                    }

                }

            }

    }

    if(!ok){

        fout << "Ciclu negativ!";

        return 0;

    }

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

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

}