#include <stdio.h>
#include <climits>
#include <queue>
#include <vector>
#define NMAX 50005
#define INF INT_MAX
using namespace std;
 
int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	int n, m, x, y, c;
    scanf("%d %d ", &n, &m);
	vector<vector<pair<int,int> > > neigh(NMAX);
	priority_queue<int> q;
	vector<int> dist(NMAX, INF), v(NMAX), viz(NMAX);
    for(int i = 1; i <= m; ++i){
		scanf("%d %d %d ", &x, &y, &c);
        neigh[x].push_back(make_pair(y,c));
    }
    q.push(1), dist[1] = 0;
    while(!q.empty()){
        int nod = q.front();
		q.pop();
        v[nod]++;
        if(v[nod] > n){
            printf("Ciclu negativ!");
            return 0;
        }
		for(int i = 0; i < neigh[nod].size(); ++i)
            if(dist[neigh[nod][i].first] > dist[nod] + neigh[nod][i].second){
				dist[neigh[nod][i].first] = dist[nod] + neigh[nod][i].second;
				q.push(neigh[nod][i].first);
			}
	}
    for(int i = 2; i <= n; ++i)
        printf("%d ", dist[i]);

	return 0;
}