#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct NODE
{
    int to;
    int cost;
};
int n,m;
vector<NODE> g[50005];
int cost[50005];
int viz[50005];
queue<int> q;

bool negativ=false;
int main()
{
    in>>n>>m;
    while(m--)
    {
        NODE node;
        int x;
        in>>x>>node.to>>node.cost;
        g[x].push_back(node);
    }
    for(int i=1; i<=n; i++) cost[i]=1e9;

    q.push(1);
    cost[1]=0;
    while(!q.empty())
    {
        int fr=q.front();

        viz[fr]++;
        if(viz[fr]==n)
        {
            negativ=true;
            break;
        }

        for(auto it:g[fr])
        {
            int newCost=cost[fr]+it.cost;
            if(newCost<cost[it.to])
            {
                cost[it.to]=newCost;
                q.push(it.to);
            }
        }
        q.pop();
    }

    if(negativ) out<<"Ciclu negativ!";
    else
    {
        for(int i=2; i<=n; i++)
            out<<cost[i]<<' ';
    }
    return 0;
}