#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,x,y,c,d[50002],lg[50002],terminare;
bool marker[50002];
vector <pair< int,int> >G[50002];
queue <int >q;
void solve()
{
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        marker[x]=false;
        for(int i=0;i<G[x].size();i++)
        {
            int cost=G[x][i].first;
            int y=G[x][i].second;
            if(d[x]+cost<d[y])
            {
                d[y]=d[x]+cost;
                lg[y]=lg[x]+1;
                if(lg[y]>n)
                {
                    terminare=1;
                    break;
                }
                if(!marker[y])
                {
                    q.push(y);
                    marker[y]=true;
                }
            }
        }
        if(terminare==1)break;
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[x].push_back({c,y});
    }
    for(int i=2;i<=n;i++)
    {
        d[i]=2000000000;
        marker[i]=false;
    }
    marker[1]=true;
    lg[1]=1;
    solve();
    if(terminare==1)g<<"Ciclu negativ!"<<'\n';
    else
    {
        for(int i=2;i<=n;i++)
        {
            g<<d[i]<<" ";
        }
    }
    return 0;
}