#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define double long double
#define endl '\n'
#define sz size
#define pb push_back
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
int const INF = LONG_LONG_MAX;

int n, m;
vector<pair<int, int> > adj[50005];

vector<int> d(50005, INF), cnt(50005, 0);
vector<bool> inq(50005, 0);
queue<int> q;

bool SPFA()
{
    while(!q.empty())
    {
        int v=q.front();
        inq[v]=0;
        q.pop();
        for(auto edge:adj[v])
        {
            int to=edge.fs, len=edge.sc;
            if(d[to]>d[v]+len)
            {
                d[to]=d[v]+len;
                q.push(to);
                inq[to]=1;
                cnt[to]++;
                if(cnt[to]>=n) return 0;
            }
        }
    }
    return 1;
}

void solve()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        cin>>x>>y>>c;
        adj[x].pb({y, c});
    }
    d[1]=0;
    q.push(1);
    cnt[1]++;
    inq[1]=1;
    if(!SPFA()){cout<<"Ciclu negativ!";}
    else
    {
        for(int i=2;i<=n;i++)
            cout<<d[i]<<' ';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int tc=1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
    return 0;
}