#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

#define INF 0x3f3f3f3f

vector<pair<int,int> > ADJ[50005];

int dist[50005],ciclu[50005];

int N,M;

queue<int> Q;

bool Bellman_Ford ()
{
    while (!Q.empty())
    {
        int cur=Q.front();
        Q.pop();
        ++ciclu[cur];
        if (ciclu[cur]==N)
        {
            return 0;
        }
        vector<pair<int,int> > :: iterator it;
        for (it=ADJ[cur].begin();it!=ADJ[cur].end();++it)
        {
            int nod=(*it).first;
            int cost=(*it).second;
            if (dist[cur]+cost<dist[nod])
            {
                dist[nod]=cost+dist[cur];
                Q.push(nod);
            }
        }
    }
    return 1;
}

int main()
{
    fin >> N >> M;
    int i;
    for (i=1;i<=M;++i)
    {
        int x,y,cost;
        fin >> x >> y >> cost;
        ADJ[x].push_back({y,cost});
    }
    for (i=2;i<=N;++i)
    {
        dist[i]=INF;
    }
    dist[1]=0;
    Q.push(1);
    if (Bellman_Ford()==0)
    {
        fout << "Ciclu negativ!";
    }
    else
    {
        for (i=2;i<=N;++i)
        {
            fout << dist[i] << " ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}