#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define fo(i, n) for (i = 0; i < n; i++)
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s) 
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s) 
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x)) 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pl; 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<pii> vpii;
#define INF 1000000000
#define NMAX 50001
string file = "bellmanford";

ifstream fin(file+".in");
ofstream fout(file+".out");

int n,m;
int dmin[NMAX];
int nr[NMAX];
vector<pair<int,int>>G[NMAX];
bool negativ;
queue<int>C;
void read();
void display();
void BellmanFord();

int main() 
{
    read();
    BellmanFord();
    display();
    fin.close();
    fout.close();
    return 0;
}

void read(){
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}

void BellmanFord()
{
    vector<pair<int,int>> ::iterator it;
    int i,x;
    for(i=1;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 display()
{
    if(negativ)
    {
        fout<<"Ciclu negativ!";
    }
    else{
        for(int i=2;i<=n;i++)
            if(dmin[i] != INF)
            {
                fout<<dmin[i]<<" ";
            }
            else
            {
                fout<<0<<" ";
            }
            
    }
}