#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

class muchie
{
public:
    int from;
    int to;
    int cost;
    muchie(int from, int to, int cost):
        from(from), to(to), cost(cost)
        {

        }
};

int n,m;
vector<muchie> edges;
int dist[50005];

int bellman(int s)
{
    dist[s] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (auto& m: edges)
        {
            if (dist[m.from] + m.cost < dist[m.to])
                dist[m.to] = dist[m.from] + m.cost;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (auto& m: edges)
        {
            if (dist[m.from] + m.cost < dist[m.to])
                return -1;
        }
    }

    return 0;
}

int main()
{
    f >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x,y,c;
        f >> x >> y >> c;
        edges.push_back({x,y,c});
    }

    for (int i = 1; i <= n; i++)
        dist[i] = 1000000000;

    int st = bellman(1);

    if (st == -1)
    {
        g << "Ciclu negativ!";
        return 0;
    }

    for (int i = 2; i <= n; i++)
        g << dist[i] << ' ';

    return 0;
}