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

using namespace std;

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

const int INF=1e9;
const int N=5e4+5;

struct edge{
    int to;
    int cost;
};

vector<edge> gr[N];
bool inq[N];
int nr[N];

int main()
{
    int n, m;
    in>>n>>m;
    while(m--){
        int x, y, c;
        in>>x>>y>>c;
        gr[x].push_back({y, c});
    }
    vector<int>d(n+1, INF);
    d[1]=0;
    queue<int> q;
    q.push(1);
    inq[1]=true;
    bool ok=true;
    while(!q.empty() && ok){
        auto nod = q.front();
        inq[nod] = false;
        q.pop();
        for(auto e:gr[nod])
        {
            int cost = d[nod] + e.cost;
            if(cost<d[e.to])
            {
                d[e.to] = cost;
                if(!inq[e.to]){
                    if(++nr[e.to]>n-1)
                    {
                        ok=false;
                        break;
                    }
                    inq[e.to]=true;
                    q.push(e.to);
                }
            }
        }
    }
    if(ok)
    {
        for(int i=2; i<=n; ++i)
        {
            out<<d[i]<<' ';
        }
    }
    else
    {
        out<<"Ciclu negativ!\n";
    }
    return 0;
}