#include <bits/stdc++.h>

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

#define inf 10000
vector<pair<int, int>> v[50001];
vector<int> dist;
queue<int> coada;
int N, inCoada[50001], vizitat[50001];
bool cicl=false;

// Pentru a obține 100 de puncte, îmbunătăţirea costului nodurilor vecine se face introducându-le într-o coadă în cazul scăderii costului, dacă nu apar deja.
bool BMF(int src)
{
    dist[src]=0;
    coada.push(src);
    inCoada[src] = 1;
    while(!coada.empty())
    {
        int i = coada.front();
        coada.pop();
        inCoada[i] = 0;
        vizitat[i]++;
        if(vizitat[i] >= N) return false;
        for(auto element: v[i])
        {
            int j=element.first, w=element.second;
            if(dist[j] > dist[i] + w)
            {
                dist[j] = dist[i] + w;
                if(inCoada[j]==0)
                {
                    coada.push(j);
                    inCoada[j] = 1;
                }
            }
            
            /*
            if(dist[j] > dist[i] + w)
            {
                dist[j] = dist[i] + w;
                fout << i << " -(" << dist[j] << ")-> " << j << "\n";
            }
            */
        }
    }
    return true;
    /*
    for(int i=1; i<=N; i++)
    {
        for(auto element: v[i])
        {
            int j=element.first, w=element.second;
            if(dist[j] > dist[i] + w)
            {
                cicl=true;
                return ;
            }
        }
    }
    */
}

int main()
{
    int M;
    fin >> N >> M;
    for(int i=1; i<=M; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for(int i=0; i<=N; i++) dist.push_back(inf);
    if(BMF(1))
        for(int i=2; i<=N; i++)
            fout << dist[i] << " ";
    else
        fout << "Ciclu negativ!";
    return 0;
}