#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const string filename = "bellmanford";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int maxN = 50005, inf = 0x3f3f3f3f;
int n, m, used[maxN], dist[maxN];
bool prost;
struct Node {
    int nod, cost;
};
vector <Node> G[maxN];
queue <int> q;

void bfs(int start)
{
    for(int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[start] = 0;
    q.push(start);
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        used[curr]++;
        if(used[curr] > n)
        {
            prost = 1;
            return;
        }
        for(Node nxt : G[curr])
        {
            if(dist[curr] + nxt.cost < dist[nxt.nod])
            {
                dist[nxt.nod] = dist[curr] + nxt.cost;
                q.push(nxt.nod);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int x, y, c, i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }
    bfs(1);
    if(prost)
    {
        fout << "Ciclu negativ!";
        return 0;
    }
    for(int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    return 0;
}