#include <fstream>
#include <queue>
#include <vector>
#define DIM 50001
using namespace std;
ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");
vector<pair<int,int> > V[DIM];
queue<int> Q;
int n,m;
int a,b,c;
int F[DIM],L[DIM];
bool cic;
int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fi>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
    }
    Q.push(1);
    L[1]=0;
    while(!Q.empty() && !cic)
    {
        int v=Q.front();
        F[v]++;
        if(F[v]==n)
            cic=true;
        for(int i=0;i<V[v].size();i++)
            if(L[V[v][i].first]==0 || L[v]+V[v][i].second<L[V[v][i].first])
            {
                Q.push(V[v][i].first);
                L[V[v][i].first]=L[v]+V[v][i].second;
            }
        Q.pop();
    }
    if(cic)
        fo<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fo<<L[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}