#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct edge{
    int node;
    int cost;
    int used;

    edge(int node, int cost, int used){
        this->node = node;
        this->cost = cost;
        this->used = used;
    }
};

vector< edge > v[50010];
queue< int > coada;

int main()
{
    int n, m;
    fin >> n >> m;

    int a, b, c;
    for(int i = 0; i < m; i++){
        fin >> a >> b >> c;
        v[a].push_back( edge(b, c, 0) );
    }

    int dist[50010];
    for(int i = 0; i < 50010; i++)
        dist[i] = 1000000000;

    dist[1] = 0;
    coada.push( 1 );
    while(!coada.empty()){
        int now = coada.front();
        coada.pop();

        for(auto &it: v[now]){
            int nxt = it.node;

            if(dist[nxt] > dist[now] + it.cost){
                dist[nxt] = dist[now] + it.cost;
                coada.push(nxt);

                it.used++;
                if(it.used >= n){
                    fout << "Ciclu negativ!";
                    exit(0);
                }
            }
        }
    }

    for(int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    return 0;
}