#include <bits/stdc++.h>

using namespace std;
const int NMAX = 50005;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m;
vector<pair<int, int>> graf[NMAX];
struct muchie
{
    int x,y,c;
};
int dist[NMAX];
bool inCue[NMAX];
int c[NMAX];
queue<int> cue;
int main()
{
    fin>>n>>m;
    vector<muchie> muchii;
    for(int i = 0; i<m; i++)
    {
        int a, b, c;
        fin>>a>>b>>c;
        graf[a].push_back({b,c});
    }
    fill(dist,dist+NMAX,213123123);
    dist[1]=0;
    inCue[1]=1;
    cue.push(1);
    c[1]++;
    bool neg = false;
    while(cue.size() && (!neg))
    {
        int j = cue.front();
        cue.pop();
        inCue[j]=false;
        for(auto i:graf[j])
        {
            if(dist[i.first]>dist[j]+i.second)
            {
                dist[i.first]=dist[j]+i.second;
                if(!inCue[i.first])
                {
                    if(c[i.first]>n)
                    {
                        neg = true;
                    }
                    else
                    {
                        cue.push(i.first);
                        inCue[i.first]=true;
                        c[i.first]++;
                    }
                }
            }
        }
    }


    if(neg)
        fout<<"Ciclu negativ!";
    else
        for(int i = 2; i<=n; i++)
            fout<<dist[i]<<" ";
    return 0;
}