#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int N_MAX = 50001;
const int M_MAX = 250001;
const int POSITIVE_INFINITY = 1000000000;
const int NEGATIVE_INFINITY = -1000000000;

struct Vertex
{
    int at, to, cost;
}node[M_MAX];

int n, m;
vector <int> dist(N_MAX, POSITIVE_INFINITY);

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> node[i].at >> node[i].to >> node[i].cost;
    }
}

bool BellmanFord(int startNode)
{
    dist[startNode] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (dist[node[j].at] + node[j].cost < dist[node[j].to])
            {
                dist[node[j].to] = dist[node[j].at] + node[j].cost;
            }
        }
    }

    for (int j = 1; j <= m; j++)
    {
        if (dist[node[j].at] + node[j].cost < dist[node[j].to])
        {
            //dist[node[j].to] = NEGATIVE_INFINITY;
            return false;
        }
    }

    return true;
}

int main()
{
    Read();
    if (BellmanFord(1) == false)
    {
        g << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            g << dist[i] << " ";
        }
    }
}