#include <iostream>
#include <limits.h>
#include <cmath>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <map>
#include <fstream>
#include <list>
#include <queue>
#include <iomanip>
#include <deque>
#include <set>

using namespace std;

#define mm 50001
#define inf (1<<30)
#define pb push_back
#define mp make_pair

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define cin f
#define cout g

int dist[50001],prec[50001];
vector<int> v[50001],w[50001];

void Init(int n)
{
    dist[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        dist[i] = inf;
        prec[i] = -1;
    }
}

void BellmanFord(int n)
{
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < v[i].size(); j++)
            if (w[i][j] + dist[i] < dist[v[i][j]])
    {
        dist[v[i][j]] = w[i][j] + dist[i];
        prec[v[i][j]] = i;
    }
}

int Verific(int n)
{
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < v[i].size(); j++)
            if (w[i][j] + dist[i] < dist[v[i][j]])
            {
                cout<<"Ciclu negativ!";
                return 0;
            }

    for(int i = 2; i <= n; i++)
        cout<<dist[i]<<" ";
}

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        v[x].pb(y);
        w[x].pb(z);
    }

    Init(n);
    BellmanFord(n);
    Verific(n);

 return 0;
}