#include <iostream>
#include <climits>
#include <vector>
#include <fstream>
#define VMAX 50000
#define NIL -1
#define EMAX 250000
using namespace std;

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

class Edge
{
public:
    int x, y;
    short w;
    Edge(int x = 0, int y = 0, short w = 0) : x(x), y(y), w(w) {}
};

int V, E, x, y, w, src, u, v;
vector <int> d(VMAX, INT_MAX);
Edge edges[EMAX];
vector <int> parent(VMAX, NIL);

void afisare(int u)
{
    if (u != src - 1)
    {
        afisare(parent[u]);
        fout << u + 1 << " ";
    }
}

int main()
{
    src = 1;
    fin >> V >> E;

    for (int i = 0; i < E; ++i)
    {
        fin >> x >> y >> w;
        edges[i] = Edge(x - 1, y - 1, w);
    }

    d[0] = 0;

    int x = 0;
    int contor = 0;

    while (x >= 0 && contor < V)
    {
        x = -1;
        contor++;
        for (int j = 0; j < E; ++j)
        {
            u = edges[j].x;
            v = edges[j].y;
            w = edges[j].w;
            if (d[u] != INT_MAX && d[v] > d[u] + w)
                d[v] = d[u] + w, x = v, parent[v] = u;
        }
    }

    if (x >= 0)
        fout << "Ciclu negativ!";

    else for (int i = 1; i < V; ++i)
            fout << d[i] << " ";

    fin.close();
    fout.close();
    return 0;
}