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

using namespace std;

string problema = "bellmanford";

ifstream in(problema+".in");
ofstream out(problema+".out");

int n,m;
struct nodeCost{
    int to;
    int cost;
};
vector<nodeCost> nod[50001];
queue<int> toVisit;
int cost[50001];
int timesPassed[50001];
bool inQueue[50001];

int main()
{
	in>>n>>m;
	for(int i = 1;i<=m;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        nodeCost node;
        node.cost=c;
        node.to=y;
        nod[x].push_back(node);
    }
    for(int i = 2;i<=n;i++)
    {
        cost[i]=0x3f3f3f3f;
    }
    toVisit.push(1);
    while(!toVisit.empty())
    {
        for(nodeCost node : nod[toVisit.front()])
        {
            int newCost = cost[toVisit.front()]+node.cost;
            if(newCost<cost[node.to])
            {
                cost[node.to]=newCost;
                if(!inQueue[node.to]){
                    if(timesPassed[node.to]<=n)
                    {
                        timesPassed[node.to]++;
                        {
                            toVisit.push(node.to);
                            inQueue[node.to]=1;
                        }
                    }
                    else
                    {
                        cicluNegativ=1;
                    }
                }
            }
        }
        inQueue[node.to]=0;
        toVisit.pop();
    }
    if(cicluNegativ)
    {
        out<<"Ciclu negativ!";
        return 0;
    }
    for(int i = 2;i<=n;i++)
    {
        out<<cost[i]<<' ';
    }
    return 0;
}