#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
#include <set>

using namespace std;
 
const int NMAX = 50005;
const int INF = 0x3f3f3f3f;

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

struct muchie
{
    long a, b, c;
} e[NMAX];

long n, m, cost[NMAX], f[NMAX];
vector <long> v[NMAX];
vector < pair<long, long> > h;

int main() {
	in >> n >> m;
	
    cost[1] = 0;
    for(int i = 2; i <= n; i++)
        cost[i] = INF;
        
    for(int i = 1; i <= m; i++)
    {
        in >> e[i].a >> e[i].b >> e[i].c;
        v[e[i].a].push_back(i);
    }    
    
    h.push_back(make_pair(0, 1));
    make_heap(h.begin(), h.end());
    
    pair<long, long> per;
    long nod, poz;
    long long pas=0;
    
    while(h.size() && pas <= 1LL * n * m)
    {
        pas++;
        pop_heap(h.begin(), h.end());
        per = h.back();
        h.pop_back();
        nod = per.second;
        f[nod] = 0;
        for(int j = 0; j < v[nod].size(); j++)
        {
            poz = v[nod][j];
            if(cost[e[poz].a] + e[poz].c < cost[e[poz].b])
            {
                cost[e[poz].b] = cost[e[poz].a] + e[poz].c;
                if(!f[e[poz].b])
                {
                    f[e[poz].b] = 1;
                    h.push_back(make_pair(-cost[e[poz].b], e[poz].b));
                    push_heap(h.begin(), h.end());
                }
            }
        }
    }
    
    int contor = 0;
    
    for(int i=1; i<= m; i++) {
        if(cost[e[i].a] + e[i].c < cost[e[i].b])
            contor = 1;
    }
            
	if (contor) {
		out << "Ciclu negativ!";
	} else {
		for(int i = 2; i <= n; i++)
        	out << cost[i] << " ";
    	out << endl;
	}
	
	return 0;
}