#include <fstream>
#include <vector>

using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
#define N 50005
#define INF 1e9
vector < pair < int, int> > vec[N];
int n,m,d[N];
void read()
{
    int i,j,x,y,c;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        vec[x].push_back({y,c});
    }
}
void solve()
{
    int i,j;
    bool ok=true;
    for(i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    for(i=1; i<n; i++)
        for(j=1; j<=n; j++)
        {
            for(auto x:vec[j])
            {
                if(d[x.first]>d[j]+x.second)
                    d[x.first]=d[j]+x.second;

            }
        }
    for(j=1; j<=n; j++)
    {
        for(auto x:vec[j])
        {
            if(d[x.first]>d[j]+x.second)
            {
                ok=false;
                break;
            }
        }
    }
    if(ok==1)
    {
        for(i=2;i<=n;i++)
            cout<<d[i]<<" ";
    }
    else cout<<"Ciclu negativ!";
}
int main()
{
    read();
    solve();
    return 0;
}