#include <iostream>
#include <vector>
#include <fstream>
#define node pair<int,int>
using namespace std;

const char nl = '\n';
const int inf = 1e9 + 2;
const int NMAX = 5 * 1e4 + 5;
vector<node> graph[NMAX];
int dist[NMAX];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
void bellmanford (int source, int n) {
    for (int i = 2; i <= n; i++) {
        dist[i] = inf;
    }
    for (int i = 1; i <= n - 1;i++) {
        for (int j = 1; j <= n; j++) {
            for (auto neigh: graph[j]) {
                if (neigh.second + dist[j] < dist[neigh.first]) {
                    dist[neigh.first] = neigh.second + dist[j];
                }
            }
        }
    }
    for (int j = 1; j <= n; j++) {
        for (auto neigh: graph[j]) {
                if (neigh.second + dist[j] < dist[neigh.first]) {
                   dist[0] = -1;
                }
            }
    }
   
}
int main () {
    int n,m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x,y,z;
        fin >> x >> y >> z;
        graph[x].push_back({y,z});
       
    }
    bellmanford(1,n);
    if (dist[0] == -1) {
        fout << "Ciclu negativ!";
    }
    else 
    {
        for (int i = 2; i <= n; i++) {
        fout << dist[i] << " ";
        }
    }
   
}