#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define NMAX 50010
using namespace std;

ifstream fi("bellmanford.in"); void Input();
ofstream fo("bellmanford.out"); void Output();

struct Node
{
    int node, cost;
    Node(int aNode, int aCost)
    {
        node = aNode;
        cost = aCost;
    }
};

int N,M;
bool infinit;
int contor[NMAX];
int dist[NMAX];
queue<int> q;
vector<Node> graph[NMAX];

void bellmanFord(int start)
{
    q.push(start);
    ++contor[start];
    dist[start] = 0;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(auto y:graph[x])
        {
            
            if(dist[y.node] > dist[x] + y.cost)
            {
                if(y.node == x) continue;
                dist[y.node] = dist[x] + y.cost;
                q.push(y.node);
                ++contor[y.node];
                if(contor[y.node] == N)
                {
                    infinit = true;
                    return;
                }
            }
        }
    }
}

int main()
{
    Input();
    bellmanFord(1);
    Output();
}

void Input()
{
    fi>>N>>M;
    int x,y,k;
    for(int i=1; i<=M; ++i)
    {
        fi>>x>>y>>k;
        graph[x].push_back(Node(y,k));
    }
    for(int i = 1; i <= N; ++i)
    {
        dist[i] = INF;
    }
}
void Output()
{
    if(!infinit) 
    {
        for(int i=2; i<=N; ++i)
        {
            fo<<dist[i]<<" ";
        }
    }
    else
    {
        fo<<"Ciclu negativ!";
    }
}