#include <bits/stdc++.h>

using namespace std;

int n,m;

vector < pair<int,int> > v[50001];
pair <int,int> elem;
int ind,aux=false;
int dist[50001];
int deCate[50001];
queue <int> q;
void bellmanford(int n)
{
    q.push(n);
    while(!q.empty())
    {
        n=q.front();
        q.pop();
        for (int i=0; i<v[n].size(); i++)
        {
            if (deCate[v[n][i].first]==::n)
            {
                ::aux=true;
                return;
            }
            if ((dist[n]+v[n][i].second)<dist[v[n][i].first])
            {
                dist[v[n][i].first]=dist[n]+v[n][i].second;
                deCate[v[n][i].first]+=1;
                q.push(v[n][i].first);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin>>n>>m;
    //distance[1]=0;
    for (int i=2; i<=n; i++)
    {
        dist[i]=(2<<30)-1;
    }
    for (int i=1; i<=m; i++)
    {
        cin>>ind;
        cin>>elem.first>>elem.second;
        v[ind].push_back(elem);
    }

    bellmanford(1);

    /*
    for (int i=2; i<=n; i++){
        if(dist[i]>=0) aux=true;
    */
    if(aux) cout<<"Ciclu negativ!\n";
    else
        for (int i=2; i<=n; i++)
            cout<<dist[i]<<" ";

    return 0;
}