#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, 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.
// Practic, daca nu am gasit un drum mai scurt spre un nod, nu are sens sa il verificam din nou ca un posibil mod de a scurta alte drumuri
bool BMF(int src)
{
    dist[src]=0;
    coada.push(src);
    while(!coada.empty())
    {
        int i = coada.front();
        coada.pop();
        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;
                coada.push(j);
            }
        }
    }
    return true;
}

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;
}