#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int inf=1e10;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int, int>> g[50005];
bitset<50005> in_q(false);
vector<int> dist(50005, inf);
int n, m, cnt[50005];
bool fnd;
void bf(int start)
{
    queue<int> q;
    q.push(start), dist[start]=0, in_q[start]=true;
    while(!q.empty()&&!fnd)
    {
        int nd=q.front();
        q.pop();
        for(auto &x:g[nd])
        {
            if(dist[nd]+x.second<dist[x.first])
            {
                dist[x.first]=dist[nd]+x.second;
                if(!in_q[x.first])
                {
                    if(cnt[x.first]>=n)
                    {
                        fnd=true;
                    }
                    else
                    {
                        cnt[x.first]++;
                        q.push(x.first);
                        in_q[x.first]=true;
                    }
                }
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    int x, y, c;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        g[x].pb({y, c});
    }
    bf(1);
    if(fnd)
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2; i<=n; i++)
    {
        fout<<dist[i]<<" ";
    }
    return 0;
}