#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#define ull unsigned long long
#define mod 1000000007
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,1e9);
    d[1]=0;
    for(int i=0;i<n;i++)
    {
        for(auto edge:adj)
        {
            int u=get<0>(edge);
            int v=get<1>(edge);
            int wt=get<2>(edge);

            if(d[u]!=1e9 && d[v]>d[u]+wt)
            {
                if(i==n-1)
                {
                    g<<"Ciclu negativ!";
                    return;
                }
                d[v]=d[u]+wt;
            }
        }
    }
    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;
}