#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

#define INF 0x3f3f3f3f
#define MAXN 50005

struct grf {
    int nod, cost;
}aux;

vector<grf> graf[MAXN];
queue<int> coada;
int cost[MAXN], nrc[MAXN];
int n, m;

int main() {
    int i, j, x, y, z, crt;
    bool negativ = false;
    cin >> n >> m;
    
    for(i=1; i<=m; i++) {
        cin >> x >> y >> z;
        aux.nod = y;
        aux.cost = z;
        graf[x].push_back(aux);
    }
    
    for(i=1; i<=n; i++)
        cost[i] = INF;
    
    
    cost[1] = 0;
    coada.push(1);
    while(!coada.empty()) {
        crt = coada.front(); coada.pop();
        
        for(j=0; j < graf[crt].size(); j++) {
            if( cost[ graf[crt][j].nod ] > cost[crt] + graf[crt][j].cost ) {
                if(nrc[ graf[crt][j].nod ] > n )
                    negativ = true;
                else {
                    nrc[ graf[crt][j].nod ]++;
                    cost[ graf[crt][j].nod ] = cost[crt] + graf[crt][j].cost;
                    coada.push( graf[crt][j].nod );
                }
                
            }
        }
    }
    if(negativ)
        cout<<"Ciclu negativ!";
    else
        for(i=2; i<=n; i++)
            cout<<cost[i]<<" ";
    
    return 0;
}