#include <iostream>
#include <fstream>
#include <utility>
#include <vector>

using namespace std;

#define MAX_NODURI 50005
#define MAX_MUCHII 250005
#define INF 999999

vector<pair<int, pair<int, int> > > muchii;
vector<int> cost[MAX_NODURI];
int dist[MAX_NODURI];

int N, M;

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        f>>x>>y>>c;
        muchii.push_back(make_pair(c, make_pair(x, y)));
    }

    for(int i = 1; i <= N; i++)
    {
        dist[i] = INF;
    }
    dist[1] = 0;
    for(int i = 1; i <= N-1; i++) //relaxam de n-1 ori
    {
        for(int j = 0; j < muchii.size(); j++)
        {
            int x, y, c;
            c = muchii[j].first;
            x = muchii[j].second.first;
            y = muchii[j].second.second;
            //cout<<"x: "<<x<<" y: "<<y<<endl;
            if(dist[x] + c < dist[y])
            {
                dist[y] = dist[x] + c;
            }
        }
    }
    int p = 0;
    for(int i = 1; i <= N-1; i++) //relaxam de n-1 ori
    {
        for(int j = 0; j <= muchii.size(); j++)
        {
            int x, y, c;
            c = muchii[i].first;
            x = muchii[i].second.first;
            y = muchii[i].second.second;
            if(dist[x] + c < dist[y])
            {
                p = 1;
            }
        }
    }
    if(p == 1) g<<"Ciclu negativ!";
    else
    for(int i = 2; i <= N; i++) g<<dist[i]<<" ";
    return 0;
}