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

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

const int MAX = 5e4 + 1;

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

bool in_q[MAX];

int a_intrat[MAX];

queue <int> q;

struct muhcie{

    int y , c;
};

vector <muhcie> g[MAX];

int main(){

    cin >> n >> m;

    while(m--){

        cin >> x >> y >> c;

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

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

        dp[i] = 1e9;
    }

    q.push(1);

    dp[1] = 0;

    in_q[1] = 1;

    a_intrat[1] = 1;

    while(!q.empty()){

        x = q.front();

        if(a_intrat[x] > n){

            cout << "Ciclu negativ!";

            return 0;
        }

        q.pop();

        in_q[x] = 0;

        for(auto it : g[x]){

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

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

                if(!in_q[it.y]){

                    q.push(it.y);

                    in_q[it.y] = 1;

                    a_intrat[it.y]++;
                }
            }
        }
    }

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

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

    return 0;
}