#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define INF 999999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m;
struct vertex
{
    int target;
    int cost;
};
vector<int> in_q;
vector<int> roads;
queue<int> q;
vector< vector<vertex> > mat;
int main()
{
    fin>>n>>m;
    vector<vertex> vrtx;
    mat.assign(n,vrtx);
    in_q.assign(n,0);
    roads.assign(n,INF);
    roads[0] = 0;
    int k1,k2,k3;
    for(int i=0;i<m;i++)
    {
        fin>>k1>>k2>>k3;
        vertex v;
        v.target = k2-1;
        v.cost = k3;
        mat[k1-1].push_back(v);
    }
    bool negative_cycle = false;
    q.push(0);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        in_q[x]++;
        if(in_q[x] > n)
        {
            negative_cycle = true;
            break;
        }
        for(int i=0;i<mat[x].size();i++)
        {
            if(roads[x]+mat[x][i].cost < roads[mat[x][i].target])
            {
                roads[mat[x][i].target] = roads[x]+mat[x][i].cost;
                q.push(mat[x][i].target);
            }
        }
    }
    if(negative_cycle == true)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=1;i<roads.size();i++)
        {
            fout<<roads[i]<<" ";
        }
    }
}