#include <cstdio>
#include <vector>

using namespace std;

struct edge{int node; int cost;};
const int MAXN = 50002;
const int INF = 0x3f3f3f3f;

vector<edge> g[MAXN];
int heap[MAXN], d[MAXN], in_heap[MAXN];
int heap_size = 0;

void swapValues(int a, int b)
{
    int t = heap[a];
    heap[a] = heap[b];
    heap[b] = t;
    in_heap[heap[a]] = a;
    in_heap[heap[b]] = b;
}

void addToHeap(int node)
{
    if (in_heap[node])
    {
        int i = in_heap[node];
        while (i > 1 && d[heap[i]] < d[heap[i/2]])
        {
            swapValues(i, i/2);
            i = i/2;
        }
    }
    else
    {
        heap[++heap_size] = node;
        in_heap[node] = heap_size;
        int i = heap_size;
        while (i > 1 && d[heap[i]] < d[heap[i/2]])
        {
            swapValues(i, i/2);
            i = i/2;
        }
    }
}

void deleteTop()
{
    in_heap[heap[1]] = 0;
    heap[1] = heap[heap_size];
    in_heap[heap[1]] = 1;
    heap[heap_size] = 0;
    --heap_size;
    int vmin;
    int i = 1;
    while (1)
    {
        vmin = i;
        if (2*i <= heap_size && d[heap[2*i]] < d[heap[vmin]])
            vmin = 2*i;
        if (2*i+1 <= heap_size && d[heap[2*i+1]] < d[heap[vmin]])
            vmin = 2*i+1;
        if (i != vmin)
        {
            swapValues(i, vmin);
            i = vmin;
        }
        else
            break;
    }
}

int main()
{
    FILE *in = fopen("bellmanford.in", "r");
    FILE *out = fopen("bellmanford.out", "w");

    int n, m;
    fscanf(in, "%d%d", &n, &m);

    int x, y, c;
    edge e;
    for (int i = 1; i <= m; i++)
    {
        fscanf(in, "%d%d%d", &x, &y, &c);
        e.node = y;
        e.cost = c;
        g[x].push_back(e);
    }

    for (int i = 2; i <= n; i++)
        d[i] = INF;
    d[1] = 0;
    addToHeap(1);

    int node;
    for (long long i = 1; i <= 1LL * m * n && heap_size > 0; i++)
    {
        node = heap[1];
        deleteTop();
        for (unsigned j = 0; j < g[node].size(); j++)
            if (d[g[node][j].node] > d[node] + g[node][j].cost)
            {
                d[g[node][j].node] = d[node] + g[node][j].cost;
                addToHeap(g[node][j].node);
            }
    }

    bool found_cicle = false;
    for (int i = 1; i <= n; i++)
        for (unsigned j = 0; j < g[i].size(); j++)
        {
            if (d[g[i][j].node] > d[i] + g[i][j].cost)
            {
                found_cicle = true;
                i = n+1;
                break;
            }
        }

    if (found_cicle)
        fprintf(out, "Ciclu negativ!\n");
    else
    {
        for (int i = 2; i <= n; i++)
            fprintf(out, "%d ", d[i]);
        fprintf(out, "\n");
    }

    return 0;
}