#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#define ull unsigned long long
#define mod 1000000007
#define int long long
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector<tuple<int,int,int>> adj;
int n,m;
void bellmanford()
{
    vector<int> d(n+1,4e18);
    d[1]=0;
    for(int i=1;i<n;i++)
    {
        bool ok=false;
        for(auto edge:adj)
        {
            int u=get<0>(edge);
            int v=get<1>(edge);
            int wt=get<2>(edge);

            if(d[u]!=4e18 && d[v]>d[u]+wt)
            {
                ok=1;
                d[v]=d[u]+wt;
            }
        }
        if(!ok)
            break;
    }
    for(auto edge:adj)
        {
            int u=get<0>(edge);
            int v=get<1>(edge);
            int wt=get<2>(edge);

            if(d[u]!=4e18 && d[v]>d[u]+wt)
            {
                g<<"Ciclu negativ!";
                return;
            }
        }
    for(int i=2;i<=n;i++)
        g<<d[i]<<" ";
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        adj.push_back(make_tuple(x,y,z));
    }
    bellmanford();
    return 0;
}