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

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];
int n, m;

/*


6 8
1 2 8
1 3 10
2 4 1
4 3 -4
4 5 -1
5 6 -2
6 3 1
3 5 2

*/

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 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);

    }

    d[1] = 0;
    int x = 0;

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

        x = -1;

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

            int src = edges[j].source;
            int dest = edges[j].destination;
            int cost = edges[j].cost;

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

                d[dest] = d[src] + cost;
                last[dest] = src;
                x = dest;

            }

        }
    }

    if(x == -1){

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


    }else{

        cout << "Ciclu negativ!\n";
        /*
        for(int i = 0; i < n; i++)
            x = last[x]; // ciclul maxim cuprinde toate nodurile

        drum(x, x, 1);
        */

    }

    return 0;
}