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

using namespace std;

#define N 50005

struct coord{
    int y, c;
};

int n, m;
int d[N];

vector < coord > L[N];

int viz[N];

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void Citire()
{
    fin >> n >> m;
    coord w;
    int x;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> w.y >> w.c;
        L[x].push_back(w);
    }
}

void bellmanford(int k)
{
    queue < int > q;
    bool b = 0;
    q.push(k);
    while(!q.empty())
    {
        k = q.front();
        q.pop();
        for(int i = 0; i < L[k].size(); i++)
            if(d[L[k][i].y] > L[k][i].c + d[k] || !viz[L[k][i].y])
            {
                viz[L[k][i].y]++;
                q.push(L[k][i].y);
                d[L[k][i].y] = L[k][i].c + d[k];
                if(viz[L[k][i].y] > n)
                {
                    fout << "Ciclu negativ!";
                    b = 1;
                    break;
                }
            }
    }
    if(!b)
        for(int i = 2; i <= n; i++)
            fout << d[i] << " ";
    fout << "\n";

}

int main()
{
    Citire();
    bellmanford(1);
    return 0;
}