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

using namespace std;

#define INF 25000000

vector < pair<int, int> >  graf[50000];
vector <int> dist(50000, INF);

bool bf(int n)
{
    int h = 0;
    for(int k = 1; k <= n; ++k)
    {
        h = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < graf[i].size(); ++j)
            {
                if(dist[graf[i][j].first] > dist[i] + graf[i][j].second)
                {
                    dist[graf[i][j].first] = dist[i] + graf[i][j].second;
                    h = 1;
                }
            }
        }
    }
    if(h == 1)
        return false;
    return true;
}

int main()
{
    ifstream in("bellmanford.in");
    ofstream out ("bellmanford.out");

    if(!in)
    {
        cout << "eroare";
        return -1;
    }

    int n, m;
    in >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        int a, b, cost;

        in >> a >> b >> cost;
        b--;
        graf[a-1].push_back({b, cost});
    }

    dist[0] = 0;

    if(!bf(n))
        out << "Cicluri negative!";
    else
    {
        for(int i = 1; i < n; ++i)
            out << dist[i] << " ";
    }
}