/*#include <cstdio>
#include <vector>
#include <queue>
 
#define NMAX 50001
#define INF (1 << 30)
 
using namespace std;
 
vector < pair <int, int> > G[NMAX];
queue <int> q;
 
int N;
int d[NMAX];
int viz[NMAX];
 
int main () {
	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);
	int M, i, x, y, c, m;
	
	//read
	scanf ("%d %d", &N, &M);
	for (i = 1; i <= M; ++i) {
		scanf("%d %d %d", &x, &y, &c);
		G[x].push_back(make_pair(y, c));
	}
	//
	
	//solve
	for (i = 1; i <= N; ++i)
		d[i] = INF;
	d[1] = 0;
	q.push(1);
	int ok = 1;
	while (!q.empty()) {
		x = q.front();
		q.pop();
		m = G[x].size();
		for (i = 0; i < m; ++i) {
			y = G[x][i].first;
            c = G[x][i].second;
			if (d[y] > d[x] + c) {
				d[y] = d[x] + c;
				q.push(y);
				++viz[x];
			}
		}
		if (viz[x] > N)
			ok = 0;
	}
	//
	
	//print
	if (!ok) 
		printf("Ciclu negativ!\n");
	else {
		for (i = 2; i <= N; ++i)
			if (d[i] != INF) 
				printf ("%d ", d[i]);
			else printf("0");
	}
	//
	return 0;
}
*/

//????

#include <cstdio>
#include <vector>
#include <queue>
 
#define NMAX 50001
#define INF (1 << 30)
 
using namespace std;
 
vector < pair <int, int> > G[NMAX];
queue <int> Q;
 
int n;
int d[NMAX];
int viz[NMAX];
 
void read()
{
    freopen("bellmanford.in", "r", stdin);
 
    int m;
    int x;
    int y;
    int c;
 
    scanf("%d %d", &n, &m);
    while(m --)
    {
        scanf("%d %d %d\n", &x, &y, &c);
        G[x].push_back(make_pair(y, c));
    }
}
 
int solve(int v)
{
    for(int i = 1; i <= n; d[i] = INF, ++ i);
    d[v] = 0;
 
    Q.push(v);
 
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
 
        unsigned int m = G[x].size();
        for(unsigned int i = 0; i < m; ++ i)
        {
            int y = G[x][i].first;
            int c = G[x][i].second;
 
            if(d[y] > d[x] + c)
            {
                d[y] = d[x] + c;
                Q.push(y);
                ++ viz[x];
            }
        }
 
        if(viz[x] > n)
            return 0;
    }
 
    return 1;
}
 
void write()
{
    for(int i = 2; i <= n; ++ i)
        if(d[i] != INF)
            printf("%d ", d[i]);
        else
            printf("0 ");
 
    printf("\n");
}
 
int main()
{
    freopen("bellmanford.out", "w", stdout);
 
    read();
    if(solve(1))
        write();
    else
        printf("Ciclu negativ!\n");
 
    return 0;
}