#include <cstdio>
#include <vector>

using namespace std;

struct edge {int node; int cost;};

vector<edge> g[50002];
int d[50002];
int n, m;
int heap[50002];
int heap_size;
bool in_heap[50002];
const int INF = 1000000;

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

void addToHeap(int node)
{
    in_heap[node] = 1;
    heap[++heap_size] = node;
    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];
    heap_size--;
    int i = 1;
    int vmin;
    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 (vmin != i)
            swapValues(vmin, i);
        else
            break;
        i = vmin;
    }
}

void init()
{
    d[1] = 0;
    for (int i = 2; i <= n; ++i)
            d[i] = INF;
    heap_size = 0;
    addToHeap(1);
}

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

bool negCycle()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < g[i].size(); ++j)
        {
            if (d[i] + g[i][j].cost < d[g[i][j].node])
                return 1;
        }
    return 0;
}

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

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

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

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


    fclose(in);
    fclose(out);

    return 0;
}