#include<bits/stdc++.h>
#define NMAX 50005
using namespace std;

/*************************************************/
/// INPUT / OUTPUT
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
/*************************************************/
/// GLOBAL DECLARATIONS
bool isNegativeWeightCycle = false;

int n, m;

vector < pair < int, int > >graph[NMAX];

queue<int> q;

int d[NMAX], changes[NMAX];

bool inQueue[NMAX];
/*************************************************/

///--------------------------------------------------------------------
inline void readInput()
{
    f >> n >> m;

    for(int  i = 1 ; i <= m ; ++ i)
    {
        int a , b , cost;
        f >> a >> b >> cost;

        graph[a].push_back({b, cost});
    }
    d[1] = 0;
    for(int  i = 2 ; i <= n ; ++i) d[i] = 1e5;
}
///--------------------------------------------------------------------
inline void dfs(int startNode)
{
    q.push(startNode);
    inQueue[startNode] = true;
    while(!q.empty())
    {
        int node = q.front();
        int cost = d[node];
        q.pop();
        inQueue[node] = false;

        for(auto it : graph[node])
        {
            if(d[it.first] > cost + it.second)
            {
                d[it.first] = cost + it.second;
                if(!inQueue[it.first])
                {
                    q.push(it.first);
                    inQueue[it.first] = true;
                }
                changes[it.first] ++;
                if(changes[it.first] > n)
                {
                    isNegativeWeightCycle = true;
                    return;
                }
            }
        }
    }
}
///--------------------------------------------------------------------
inline void Solution()
{
    dfs(1);
}
///--------------------------------------------------------------------
inline void Output(bool condition)
{
    if(condition) g << "Ciclu negativ!";
    else
    {
        for(int  i = 2 ; i <= n ; ++i) g << d[i] <<" ";
    }
}
///--------------------------------------------------------------------
int main()
{
    readInput();
    Solution();
    Output(isNegativeWeightCycle);
}