#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
vector<pair<int,int>> v[50001];
queue<int> q;
int dist[50001];
bool viz[50001];
int cnt[50001];
int main()
{
    int n,m;
    in>>n>>m;
    for(int i=2;i<=n;i++)
        dist[i]=2000000000;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        v[a].push_back({b,c});
    }
    q.push(1);
    bool ok=0;
    int x;
    while(!ok && !q.empty())
    {
        x=q.front();
        q.pop();
        viz[x]=0;
        for(auto y:v[x])
        {
            if(dist[y.first] > dist[x] + y.second)
            {
                dist[y.first]=dist[x]+y.second;
                if(!viz[y.first])
                {
                    if(cnt[y.first] > n)
                        ok = 1;
                    else
                    {
                        cnt[y.first]++;
                        viz[y.first] = 1;
                        q.push(y.first);
                    }
                }
            }
        }
    }
    if(ok){
        for(int i=1;i<=n;i++)
            cout<<cnt[i]<<" ";
        out<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=n;i++)
            out<<dist[i]<<' ';
    }
    return 0;
}