#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#define nmax 50002
#define inf 10000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n,m;

struct nod{
    int vecin,cost;
};

queue<pair<int, int> > coada;

vector <nod> graf[nmax];
bitset <nmax> vizitat;
int min_cost[nmax];


void in_dates()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        min_cost[i]=inf;
    }
    for(int j=1;j<=m;j++)
    {
        fin>>x>>y>>c;
        nod NOU;
        NOU.vecin=y;
        NOU.cost=c;
        graf[x].push_back(NOU);
    }
}

void bellman_ford()
{
    min_cost[1]=0;
    vizitat[1]=1;
    coada.push(make_pair(1,0));
    long long pasi=0;
    long long valoare_maxima=(long long)(n-1)* m;
    while(!coada.empty() && pasi<=valoare_maxima)
    {
        pair<int,int> x;
        x = coada.front();
        coada.pop();
        int node=x.first;
        vizitat[node]=0;
        for(int i=0;i<graf[node].size();i++)
        {
            if(min_cost[graf[node][i].vecin]>graf[node][i].cost+min_cost[node])
            {
                min_cost[graf[node][i].vecin]=graf[node][i].cost+min_cost[node];
                if(vizitat[graf[node][i].vecin]==0)
                {
                    vizitat[graf[node][i].vecin]=1;
                    coada.push(make_pair(graf[node][i].vecin,min_cost[graf[node][i].vecin]));
                }
            }
        }
        pasi++;
    }
}

void out_dates()
{
    int sol=0;
    for(int i=1;i<=n;i++)
    {
        if(min_cost[i]>=0)
        {
            sol=1;
        }
    }
    if(sol==1){
    for(int i=2;i<=n;i++)
    {
        fout<<min_cost[i]<<" ";
    }}
    else
    {
        fout<<"Ciclu negativ!";
    }
}
int main()
{
    in_dates();
    bellman_ford();
    out_dates();
    return 0;
}