#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>

using namespace std;

// #define DEBUG 1
// #if DEBUG
// std::ifstream fin("_input.txt");
// #else
// #define fin std::cin
// #endif

const int nmax = 50010;
const int inf = INT_MAX;

int n,m;
vector<vector<pair<int,int>>>graf(nmax);



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

bool BellmanFord(int nod_start,vector<vector<pair<int,int>>>&graf,vector<int>&dist)
{
    queue<int>q;
    vector<bool>viz(n,false);
    vector<int>fr(n,0);

    dist[nod_start] = 0;
    q.push(nod_start);
    viz[nod_start] = 1;

    while(!q.empty())
    {
        int el = q.front();
        q.pop();
        viz[el] = false;
        fr[el]++;
        if(fr[el] > n)
            return 0;
        for(auto i : graf[el])
        {
            int vecin = i.first;
            int cost = i.second;
            if(dist[el] + cost < dist[vecin])
            {
                dist[vecin] = dist[el] + cost;
                 if(viz[vecin] == false)
                {
                    viz[vecin] == 1;
                    q.push(vecin);
                }
            }  
        }
    }
    return 1;
}

int main()
{
   fin>>n>>m;
   for(int i = 1;i <= m;i++)
   {
        int muchie1,muchie2,cost;
        fin>>muchie1>>muchie2>>cost;
        muchie1--;
        muchie2--;
        graf[muchie1].emplace_back(make_pair(muchie2,cost));
   }
    vector<int>dist(n,inf);

    if(BellmanFord(0,graf,dist) == 0)
        fout<<"Ciclu negativ!";
    else
        for(int i = 1;i < n;i++)
            fout<<dist[i]<<" ";
    
    
}