#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int MAX = 5e4+1;

const int maximposibil = 1e9 + 1;

int dp[MAX] , n , m , x , y , c , intrari[MAX];

bool in[MAX];

struct edge{

    int y , c;
};

vector <edge> g[MAX];

queue <int> q;

int main()
{
    cin >> n >> m;

    while(m--){

        cin >> x >> y >> c;

        g[x].push_back({y,c});
    }

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

        dp[i] = maximposibil;
    }

    q.push(1);

    in[1] = 1;

    while(!q.empty()){

        x = q.front();

        q.pop();

        in[x] = 0;

        for(auto it : g[x]){

            if(dp[it.y] > dp[x] + it.c){

                dp[it.y] = dp[x] + it.c;

                if(!in[it.y]){

                    in[it.y] = 1;

                    intrari[it.y]++;

                    if(intrari[it.y] > n){

                        cout << "Ciclu negativ!";

                        return 0;
                    }

                    q.push(it.y);
                }
            }
        }
    }

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

        cout << dp[i] << ' ';
    }

    return 0;
}