#include <fstream>
#include <algorithm>
#define oo 0x7fffffff
using namespace std;

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

struct graf
{
    int nod, c;
    graf *next;
};

int n, m, dist[50001], l[50001], len, q[50003], b, e;
bool in[50001];
graf * adj[50001];


void add(int x, int y,  int c)
{
    graf *g = new graf;
    g->nod = y;
    g->c = c;
    g->next = adj[x];
    adj[x] = g;
}

void shift_left()
{
    e -= b;
    for (int i = 0; i < e; i++)
        q[i] = q[b + i];
    b = 0;
}

bool bellman()
{
    for (int i = 2; i <= n; i++)
        dist[i] = oo;

    q[0] = 1;
    e = 1;
    while (b < e)
    {
        int nod = q[b++], d = dist[nod];
        graf *g = adj[nod];
        in[nod] = 0;
        while (g)
        {
            int next = g->nod;
            if (d + g->c < dist[next])
            {
                dist[next] = d + g->c;
                l[next] = l[nod] + 1;
                if (l[next] >= n)
                    return false;
                if (!in[next])
                {
                    in[next] = 1;
                    q[e++] = next;
                    if (e > 50000)
                        shift_left();
                }
            }
            g = g->next;
        }
    }

    return true;
}

int main()
{
    int x, y, c;

    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> c;
        add(x, y, c);
    }

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