#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int viz[100001];
vector<pair<int,int>>graf_d[50001];
int distanta_bellman[50001];
int x=0;
void citire_bellman()
{
    int N,M;
    fin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        graf_d[x].push_back(make_pair(y,z));
    }
    for(int i=1;i<=N;i++)
        distanta_bellman[i]=INT_MAX;
    
    distanta_bellman[1]=0;
    priority_queue<p,vector<p>,greater<p>>heap;
    heap.push(make_pair(0,1));
    
    for(int i=1;i<=N;i++)
        viz[i]=0;
    while(!heap.empty())
    {
        int current=heap.top().second;
        heap.pop();
        viz[current]++;
        if(viz[current]>=N)
        {
            fout<<"Ciclu negativ!";
            x=1;
            break;
        }
        for(auto x:graf_d[current])
            if(distanta_bellman[current]+x.second < distanta_bellman[x.first])
            {
                distanta_bellman[x.first]=distanta_bellman[current]+x.second;
                heap.push(make_pair(distanta_bellman[x.first],x.first));
            }
    }
    if(x==0)
    for(int i=2;i<=N;i++)
        if(distanta_bellman[i]!=INT_MAX)
            fout<<distanta_bellman[i]<<" ";
        else
            fout<<0<<" ";
}
int main()
{
   citire_bellman();
}