#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;
vector<int> next_nodes_used;

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

    for (int k = 2; k <= n && nodes_used.size(); k++)
    {
        next_nodes_used.clear();
        memset(used, 0, sizeof(int) * 50005);

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

        for (auto i: nodes_used)
        {
            for (auto& m: edges[i])
                if (dist[i] + m.cost < dist[m.to])
                {
                    dist[m.to] = dist[i] + m.cost;
                    if (!used[m.to])
                    {
                        next_nodes_used.push_back(m.to);
                        used[m.to] = 1;
                    }
                }
        }

        nodes_used.swap(next_nodes_used);
    }

    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;
}