#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#define MAX 50003
using namespace std;
int d[MAX],n,m;
vector< pair<int,int> >G[MAX];
queue<int>Q;
int nr[MAX];
bool inQ[MAX];
void init()
{
    int i;
    for(i=1;i<=n;i++) d[i]=int(2e9);
    d[1]=0;
}
bool bellman()
{
    int i,nod,x;
    bool negativ=false;
    Q.push(1);
    while(!Q.empty() and !negativ)
    {
        nod=Q.front();
        Q.pop();
        inQ[nod]=false;
        x=G[nod].size();
        for(i=0;i<x and !negativ;i++)
        if(d[G[nod][i].first]>d[nod]+G[nod][i].second)
        {
            d[G[nod][i].first]=d[nod]+G[nod][i].second;
            if(!inQ[G[nod][i].first]){ if(nr[G[nod][i].first]<n)
                                {Q.push(G[nod][i].first);
                                 nr[G[nod][i].first]++;
                                 inQ[G[nod][i].first]=true;
                                } else
                                negativ=true;
                               }
        }
    }
    return negativ;
}
int main()
{
    int x,y,c,i;
    ifstream fi("bellmanford.in");
    ofstream fo("bellmanford.out");
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    init();
    if(bellman()) fo<<"Ciclu negativ!\n"; else for(i=2;i<=n;i++) fo<<d[i]<<" ";
    return 0;
}