#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;
int N;
bool cicl=false;

void BMF(int src)
{
    dist[src]=0;
    for(int i=1; i<=N-1; i++)
    {
        for(int i=1; i<=N; i++)
        {
            for(auto element: v[i])
            {
                int j=element.first, w=element.second;
                dist[j] = min(dist[j], dist[i] + w);
                /*
                if(dist[j] > dist[i] + w)
                {
                    dist[j] = dist[i] + w;
                    fout << i << " -(" << dist[j] << ")-> " << j << "\n";
                }
                */
            }
        }
    }
    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});
    }
    // fill(dist.begin(), dist.begin()+N, inf);
    for(int i=0; i<=N; i++) dist.push_back(inf);
    BMF(1);
    if(cicl) fout << "Ciclu negativ!";
    else
        for(int i=2; i<=N; i++)
            fout << dist[i] << " ";
    return 0;
}