#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

ifstream is("bellmanford.in");
ofstream os("bellmanford.out");

#define INF 0x3f3f3f3f

vector<vector<pair<int, int> > > G;
vector<int> D;
queue<int> Q;
int n, m;
bitset<50010> v;
int cnt[50010];
bool check;

void BellmanFord(int node);
void Read();


int main()
{
	Read();
	BellmanFord(1);
	if ( !check )
		for ( int i = 2; i <= n; ++i )
			os << D[i] << ' ';
	is.close();
	os.close();
	return 0;
}

void BellmanFord(int node)
{
	int x;
	D[node] = 0;
	v[node] = 1;
	Q.push(node);
	while ( !Q.empty() )
	{
		x = Q.front();
		v[x] = 0;
		Q.pop();
        for ( const auto& g : G[x] )
            if ( D[g.first] > D[x] + g.second )
            {
                D[g.first] = D[x] + g.second;
                if ( !v[g.first] )
                {
                    cnt[g.first]++;
                    if ( cnt[g.first] == n )
                    {
                        check = true;
                        os << "Ciclu negativ!";
                        return;
                    }
                    Q.push(g.first);
                    v[g.first] = 1;
                }

            }
	}
}
void Read()
{
	is >> n >> m;
	G = vector<vector<pair<int, int> > >(n + 1);
	D = vector<int>(n + 1, INF);
	int x, y, cost;
	for ( int i = 1; i <= m; ++i )
	{
		is >> x >> y >> cost;
		G[x].push_back({y, cost});
    }
}