#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int INF = 1 << 30;
int n, m, D[50003], fr[50003];
vector < pair <int, int> > G[50003];
queue <int> Q;

int main()
{
    in >> n >> m;

    for (int a, b, c, i = 1; i <= n; ++ i)
    {
        in >> a >> b >> c;
        G[a].push_back ( {b, c} );
    }

    for (int i = 2; i <= n; ++ i)
    {
        D[i] = INF;
    }

    Q.push (1);

    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        for (vector < pair <int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++ it)
        {
            int y = it -> first, cost = it -> second;
            if (D[x] + cost < D[y])
            {
                D[y] = D[x] + cost;
                ++ fr[x];
                if (fr[x] > n)
                {
                    out << "Ciclu negativ!\n";
                    out.close();
                    return 0;
                }
                Q.push(y);
            }
        }
    }

    for (int i = 2; i <= n; ++ i)
    {
        out << (D[i] == INF ? 0 : D[i]) << ' ';
    }
    out << '\n';
    return 0;
}