#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;
priority_queue <pair <long long, int> , vector <pair <long long, int>>, greater <pair <long long, int>>> q;
long long d[NMAX + 1], last[NMAX + 1];
int viz[NMAX + 1], 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 bfs(int x){

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

    while(!q.empty()){

        int node = q.top().second;
        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;
                q.push({d[dest], 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;
}