#include <iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<fstream>
#define INF 1000000000
#define NMAX 50001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
vector<pair<int, int> > G[NMAX];
int dmin[NMAX];
int nr[NMAX];
bool negativ;
queue<int> C;
void citire()
{
    int x, y, c;
    f >> n >> m ;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
}
void bellman_ford()
{
    vector<pair<int, int> > ::iterator it;
    int x;
    for(int i = 2; i <= n; i++)
        dmin[i] = INF;
    dmin[1] = 0;
    C.push(1);
    while(!C.empty() && !negativ)
    {
        x = C.front();
        C.pop();
        for(it = G[x].begin(); it != G[x].end(); it++)
            if(dmin[it->first] > dmin[x] + it->second)
            {
                dmin[it->first] = dmin[x] + it->second;
                nr[it->first]++;
                C.push(it->first);
                if(nr[it->first] > n)
                    negativ = true;
            }
    }
}
void afisare()
{
    if(negativ)
        g << "Ciclu negativ!";
    else
    {
        for(int i = 2; i <= n; i++)
            g << dmin[i] <<' ';
    }
}
int main()
{
    citire();
    bellman_ford();
    afisare();
    return 0;
}