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

using namespace std;

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

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

        }
};

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

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

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

    for (int k = 2; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (!used[i])
                continue;

            int used_this = 0;
            for (auto& m: edges[i])
                if (dist[i] + m.cost < dist[m.to])
                {
                    dist[m.to] = dist[i] + m.cost;
                    nodes_used.push_back(i);
                }
        }

        for (int i = 1; i <= n; i++)
            used[i] = 0;
        for (auto n: nodes_used)
        {
            used[n] = 1;
        }
    }

    for (int i = 1; i <= n; i++)
        for (auto& m: edges[i])
            if (dist[i] + 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[x].push_back({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;
}