#include <fstream>
#include <algorithm>

using namespace std;

#define inFile "bellmanford.in"
#define outFile "bellmanford.out"
#define MAX_V 50001
#define MAX_E 250001
#define INF 1<<30

struct EDGE {
    int x;
    int y;
    int cost;
} e[MAX_E];
int d[MAX_V];

int main() {
    ifstream in(inFile);
    ofstream out(outFile);
    
    int n, m, i, j;
    bool ERR = 0;
    
    in >> n >> m;
    for(i = 1; i <= m; i++) 
        in >> e[i].x >> e[i].y >> e[i].cost;
    for(i = 1; i <= n; i++)
        d[i] = INF;
    d[1] = 0;
        
    for(i = 1; i < n; i++) 
        for(j = 1; j <= m; j++) 
            if(d[e[j].x] + e[j].cost < d[e[j].y])
                d[e[j].y] = d[e[j].x] + e[j].cost;
        
    for(i = 1; i <= m; i++)
        if(d[e[i].y] > d[e[i].x] + e[i].cost)
            ERR = 1;
    
    if(ERR) {
        out << "Ciclu negativ!";
        return 0;
    }
    
    for(i = 2; i <= n; i++)
        out << d[i] << ' ';
    
    return 0;
}