#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

const int NMAX = 5e4;
const long long inf = 2e18;

struct bellman{

    int source, destination, cost;

};

vector <pair <int, int>> g[NMAX + 1];
vector <bellman> edges;
queue <int> q;
long long d[NMAX + 1], last[NMAX + 1];
bitset <NMAX + 1> fr;
int viz[NMAX + 1], n, m;

void drum(int x, int stop, int step){

    if(x == stop && step > 1){

        cout << x << " ";
        return;

    }

    drum(last[x], stop, step + 1);
    cout << x << " ";

}

int bfs(int x){

    d[x] = 0;
    q.push(x);

    while(!q.empty()){

        int node = q.front();
        fr[node] = 0;
        q.pop();

        if(viz[node] == n)
            return 0;

        viz[node]++;

        for(auto e : g[node]){

            int cost = e.first;
            int dest = e.second;

            if(d[dest] > d[node] + cost){

                d[dest] = d[node] + cost;

                if(!fr[dest]){

                    fr[dest] = 1;
                    q.push(dest);

                }

            }

        }

    }

    return 1;
}

int main(){

    cin >> n >> m;

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

    for(int i = 0; i < m; i++){

        int x = 0, y = 0, c = 0;

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

        bellman t;
        t.source = x;
        t.destination = y;
        t.cost = c;

        edges.push_back(t);

    }

    int x = bfs(1);

    if(x == 0){

        cout << "Ciclu negativ!";
        return 0;

    }

    for(int i = 2; i <= n; i++)
        cout << d[i] << " ";


    return 0;
}