#define MAX_N 500000
#define INF 0x3f3f3f3f

#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int start_node = 1;

struct edge_tip { int node, cost; };

int n, m, shortest_path[MAX_N + 1], edge_count[MAX_N + 1];
bool negative_cycle;
vector<edge_tip> g[MAX_N + 1];

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({ y, c });
    }
    for (int i = 1; i <= n; ++i)
    {
        shortest_path[i] = INF;
    }
    shortest_path[start_node] = edge_count[start_node] = 0;
    negative_cycle = false;
    queue<int> q;
    q.push(start_node);
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        if (edge_count[node] == n)
        {
            negative_cycle = true;
            break;
        }
        for (const edge_tip& next : g[node])
        {
            if (shortest_path[next.node] > (shortest_path[node] + next.cost))
            {
                shortest_path[next.node] = shortest_path[node] + next.cost;
                edge_count[next.node] = edge_count[node] + 1;
                q.push(next.node);
            }
        }
    }
    if (negative_cycle)
    {
        fout << "Ciclu negativ!";
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            if (i != start_node)
            {
                fout << shortest_path[i] << ' ';
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}