#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
struct duo
{
    int to,cost;
    duo(int x,int y)
    {
        to=x;
        cost=y;
    }
};
vector<vector<duo>>a;
int n;
vector<int>rez;vector<int>f;
bool bf()
{
    queue<int>q;
    q.push(1);
    rez[1]=0;
    f[1]=1;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(auto c:a[v])
        {
            if(rez[v]+c.cost<rez[c.to])
            {
                rez[c.to]=rez[v]+c.cost;
                if(++f[c.to]==n)return 0;
                q.push(c.to);

            }
        }
    }
    return 1;
}
int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int q;cin>>n>>q;
    a.resize(n+1);
    rez.resize(n+1);
    f.resize(n+1);
    for(int i=0;i<=n;i++)
    {
        rez[i]=2e9;
        f[i]=0;
    }
    for(int i=0;i<q;i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        a[x].push_back(duo(y,cost));
    }
    if(!bf())
    {
        cout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=n;i++)cout<<rez[i]<<' ';
    }
}