#include <bits/stdc++.h>
#define NMAX 50005
#define f first
#define s second
#define INF 1e9

using namespace std;

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

vector < pair < int , int > > G[NMAX];

bitset < NMAX > B;
int C[NMAX],D[NMAX];

void bellmanford(const int &n){
    int nod;
    for(int i = 2; i <= n; i++)
        D[i] = INF;
    deque < int > Q;
    Q.push_back(1);
    B[1] = 1;

    while(!Q.empty()){
        nod = Q.front();
        Q.pop_front();
        B[nod] = 0;

        for(auto const &it : G[nod]){
            if(D[it.f] <= D[nod] + it.s) continue;

            C[it.f]++;
            if(C[it.f] > n){
                fout << "Ciclu negativ!";
                return;
            }
            if(!B[it.f])
            Q.push_back(it.f);
                B[it.f] = 1;
            D[it.f] = D[nod] + it.s;
        }
    }

    for(int i = 2; i <= n; i++)
        fout << D[i] << " ";

}

int main()
{
    ios :: sync_with_stdio(false);

    int n,m,x,y,c;

    fin >> n >> m;

    for(int i = 1; i <= m; i++){

        fin >> x >> y >> c;
        G[x].push_back({y,c});

    }

    bellmanford(n);

    return 0;
}