#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int N_MAX = 1000;
const int inf = 2e28;

int main()
{
    freopen("date.in", "r", stdin);

    int n, m;
    vector<pair<int, int> > vecini[N_MAX];
    int distanta[N_MAX];
    int parinte[N_MAX];

    scanf("%d %d", &n, &m);

    for(int i = 0; i < m; i++){
        int x, y, cost;
        scanf("%d %d %d", &x, &y, &cost);
        x--;
        y--;
        vecini[x].push_back({cost, y});
    }

    for(int i = 0; i < n; i++){
        distanta[i] = inf;
        parinte[i] = -1;
    }
    distanta[0] = 0;

    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++){
            for(auto p: vecini[j]){
                if(distanta[p.second] > distanta[j] + p.first){
                    distanta[p.second] = distanta[j] + p.first;
                    parinte[p.second] = j;
                }
            }
        }
    }
    bool cicluNegativ = false;
    for(int i = 0; i < n; i++){
        for(auto p: vecini[i]){
            if(distanta[p.second] > distanta[i] + p.first){
                cicluNegativ = true;
            }
        }
    }

    if(cicluNegativ){
        printf("Ciclu negativ!!");
    }
    else{
        for(int i = 0; i < n; i++){
            if(distanta[i] == inf){
                printf("inf ");
            }
            else{
                printf("%d ", distanta[i]);
            }
        }
    }



    return 0;
}