#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define NM 50002
#define INF 250000000
using namespace std;

vector <pair <int, int>> gr[NM];

queue <int> q;

bitset <NM> qq;

int n, m, a, b, c, v[NM], cm[NM], iic[NM], cn;

void bellman_ford (int node)
{
    int t;
    q.push(node);
    iic[node]++;
    qq[node] = 1;
    cm[node] = 0;
    while(!q.empty())
    {
        t = q.front();
        if(iic[t] > n)
        {
            cn = 1;
            break;
        }
        qq[t] = 0;
        q.pop();
        for(auto i:gr[t])
        {
            if(cm[i.first] > cm[t] + i.second)
            {
                cm[i.first] = cm[t] + i.second;
                if(qq[i.first] == 0)
                {
                    q.push(i.first);

                    qq[i.first] = 1;
                }
                iic[i.first]++;

            }
        }
    }
}

int main()
{
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        gr[a].push_back(make_pair(b, c));
    }
    for(int i = 1; i <= n; i++)
        cm[i] = INF;
    bellman_ford(1);
    if(!cn)
        for(int i = 2; i <= n; i++)
            fout << cm[i] << " ";
    else
        fout << "Ciclu negativ!";
    return 0;
}