#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];

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

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

    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;
                used_this = 1;
            }
        // heuristica <3
        if (!used_this)
            used[i] = 0;
        else
            used[i] = 1;
    }

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

    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;
                used_this = 1;
                return -1;
            }
        // heuristica <3
        if (!used_this)
            used[i] = 0;
        else
            used[i] = 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;
}