#include <bits/stdc++.h>
#define FOR(i, st, dr) for(i = st; i <= dr; i++)
#define pii pair<int,int>
//#define fin cin
//#define fout cout

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 1e5 + 5, INF = 1e9;
vector < pii > edges;
vector < int > cost;
int dist[NMAX];
int n, m;

void citire()
{
    int i;
    for(i = 0; i < NMAX; ++i)
        dist[i] = INF;

    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        int a, b, c;
        fin >> a >> b >> c;
        edges.push_back({a, b});
        cost.push_back(c);
    }
}

bool ciclu = false;
void solve()
{
    int i, j;
    dist[1] = 0;
    for(i = 1; i < n; ++i)
        for(j = 0; j < edges.size(); ++j)
            if(dist[edges[j].first] + cost[j] < dist[edges[j].second])
                dist[edges[j].second] = dist[edges[j].first] + cost[j];

    for(j = 0; j < edges.size() && !ciclu; ++j)
            if(dist[edges[j].first] + cost[j] < dist[edges[j].second])
                ciclu = true;
}

int main()
{
    citire();
    solve();

    if(ciclu == true)
        fout << "Ciclu negativ!";
    else for(int i = 2; i <= n; ++i) fout << dist[i] << ' ';

    return 0;
}