#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define NMax 50005
#define pii pair<int,int>
#define inf 1e9
using namespace std;

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

int n,m,fv[NMax]= {0},cost[NMax];

vector <pii> vecini[NMax];
priority_queue <pii, vector<pii>, greater<pii>> pq;

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        vecini[x].push_back({c,y});
    }
    for(int i=1; i<=n; i++)
    {
       cost[i]=inf;
    }
    cost[1]=0;
    pq.push({cost[1],1});
    fv[1]++;
    while(!pq.empty())
    {
        int nod;
        int val;
        do
        {
            nod=pq.top().second;
            val=pq.top().first;
            pq.pop();
        }
        while(val!=cost[nod]);
        for(auto i: vecini[nod])
        {
            if(cost[i.second]>val+i.first)
            {
                fv[i.second]++;
            if(fv[i.second]==n)
            {
                fout<<"Ciclu negativ!";
                return 0;
            }
            cost[i.second]=min(cost[i.second],val+i.first);
            pq.push({cost[i.second],i.second});
            }

        }
    }
    for(int i=2;i<=n;i++)
        fout<<cost[i]<<" ";
    return 0;
}