#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define inf 0x7fffffff
#define msj "Ciclu negativ!"
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int lim=5e4+3;
int dist[lim];
vector<pair<int,int> > vec[lim];
queue<int> q;
bitset<lim> ok;
int app[lim];
int main()
{
    int n,m,x,y,c;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>c;
        vec[x].push_back({y,c});
    }
    for(int i=2;i<=n;++i)
        dist[i]=inf;
    q.push(1); dist[1]=0; ok[1]=true;
    bool stop=false;
    while(!q.empty() and !stop)
    {
        int nod=q.front();
        q.pop();
        ok[nod]=false;
        if(dist[nod]==inf)
            continue;
        for(auto t:vec[nod])
        if(dist[t.first]>dist[nod]+t.second)
        {
            dist[t.first]=dist[nod]+t.second;
            app[t.first]=app[nod]+1;
            if(app[t.first]>n-1)
                stop=true;
            if(!ok[t.first]) ok[t.first]=true,q.push(t.first);
        }
    }
    if(stop)
        cout<<msj<<'\n';
    else for(int i=2;i<=n;++i)
        cout<<dist[i]<<' ';
    return 0;
}