#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define mmax 250010
#define nmax 50010
#define inf (1<<30)
#define foor(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)
#define cout g

int n,m,i,a,b,c,nod,vecin;
struct elem{int nod,cost;};
vector <elem> G[nmax];
int dist[nmax],ccount[nmax];
queue <int> Q;
bool in_queue[nmax],negative_cicle;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        G[a].push_back({b,c});
    }
    for(i=1;i<=n;++i) dist[i]=inf;

    dist[1]=0;
    Q.push(1);
    while (!Q.empty() && !negative_cicle)
    {
        nod=Q.front();
        Q.pop();
        in_queue[nod]=false;
        foor(it,G[nod])
        if(!in_queue[it->nod] && dist[it->nod]>dist[nod]+(it->cost))
        {
            dist[it->nod]=dist[nod]+(it->cost);
            ccount[it->nod]++;
            if(ccount[it->nod]>n) negative_cicle=true;
            Q.push(it->nod);
            in_queue[it->nod]=true;
        }
    }
    if(negative_cicle) cout<<"Ciclu negativ!\n";
    else for(i=2;i<=n;++i) cout<<dist[i]<<' ';
    return 0;
}