#include <bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
#define mesaj "Ciclu negativ!"
typedef long long ll;
const ll lim=5e4+5;
const ll inf=2e9+7;
vector<pair<ll,ll> > vec[lim];
ll dist[lim];
ll pasi[lim];
ll n,m,x,y,c;
queue<pair<ll,ll> > q;
int main()
{
    in>>n>>m;
    for(ll i=1;i<=m;++i)
    {
        in>>x>>y>>c;
        vec[x].push_back({y,c});
    }
    for(ll i=2;i<=n;++i)
        dist[i]=inf;
    dist[1]=0;
    pasi[1]=0;
    q.push(make_pair(1,0));
    while(!q.empty())
    {
        ll x=q.front().first;
        ll c=q.front().second;
        q.pop();
        if(c!=dist[x])
            continue;
        if(pasi[x]>n)
        {
            out<<mesaj<<'\n';
            return 0;
        }
        for(auto p:vec[x])
        if(dist[p.first]>c+p.second)
        {
            dist[p.first]=c+p.second;
            pasi[p.first]=pasi[x]+1;
            q.push(make_pair(p.first,dist[p.first]));
        }
    }
    for(ll i=2;i<=n;++i)
        out<<dist[i]<<' ';
    return 0;
}