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

using namespace std;

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

#define Gmax 100010
#define INF 0x3f3f3f3f

vector < pair <int,int> > G[Gmax];
queue <int> q;
int dist[Gmax];
int visits[Gmax];

bool negativ = false;
int main()
{
    int N,M;
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }

    memset( dist, 0x3f, sizeof(dist));
    q.push(1);
    dist[1] = 0;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        for(int i=0;i<G[nod].size();i++)
        {
            int nextNod = G[nod][i].first;
            int nextCost = G[nod][i].second;
            if(nextCost + dist[nod]< dist[nextNod])
            {
                dist[nextNod] = nextCost + dist[nod];
                visits[nod]++;
                if(visits[nod] >= N)
                {
                    if(dist[nod] < 0)
                        negativ = true;
                    continue;
                }
                else
                    q.push(G[nod][i].first);
            }

        }
    }

    if(negativ)
        g<<"Ciclu negativ!";
    else
    for(int i=2;i<=N;i++)
        g<<dist[i]<<' ';



    return 0;
}