#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
using namespace std;

#define DEBUG
#define INFINIT 9999999

vector<pair<int,int> >graf[50001];
int n,m;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void citire()
{
    fin>>n>>m;
    while(m--)
    {
        int nod1,nod2,cost;
        fin>>nod1>>nod2>>cost;
        graf[nod1].push_back(make_pair(nod2,cost));
    }
}

int d[50001],u[50001];

void bellmanford()
{
    d[1]=0;
    u[1]++;
    for(int i=2;i<=n;i++)
        d[i]=INFINIT;

    queue<int>q;
    q.push(1);

    while(!q.empty())
    {
        int nod=q.front();
        q.pop();

        vector<pair<int,int> >::iterator it,stop=graf[nod].end();
        for(it=graf[nod].begin();it!=stop;it++)
        {
            int vecin=it->first, cost=it->second;
            if(d[vecin] > d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;

                u[vecin]++;
                if(u[vecin]>=n)
                {
                    fout<<"Ciclu negativ!\n";
                    return;
                }
                q.push(vecin);
            }

        }
    }
    for(int i=2;i<=n;i++)
        fout<<d[i]<<' ';
}

int main()
{
    citire();
    bellmanford();
    return 0;
}