#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define inf 50000100

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int N,M;
int lung[50010],nr_in_coada[50010];
bool in_coada[50010];

struct elem {
    int y,cost;
};
vector<elem> v[50010];
queue<int> C;

int main()
{
    f>>N>>M;
    FOR (i,1,M) {
        int x,y,c;
        f>>x>>y>>c;
        elem A;
        A.y=y;
        A.cost=c;
        v[x].pb(A);
    }
    FOR (i,1,N) {
        lung[i]=inf;
    }
    lung[1]=0;
    C.push(1);
    bool ciclunegativ=false;
    while (!C.empty() && !ciclunegativ) { // un nod este adaugat in coada cand se gaseste un drum mai mic pana la el
        int nod=C.front();
        C.pop();
        ++nr_in_coada[nod];
        in_coada[nod]=false;
        if (nr_in_coada[nod]>N) { // daca se incearca actualizarea vecinilor aceluiasi nod de mai mult de N ori atunci exista un ciclu negativ
            ciclunegativ=true;
        }
        else {
            for (unsigned int k=0;k<v[nod].size();++k) {
                if (lung[v[nod][k].y]>lung[nod]+v[nod][k].cost) {
                    lung[v[nod][k].y]=lung[nod]+v[nod][k].cost;
                    if (!in_coada[v[nod][k].y]) { // un nod nu se mai adauga in coada daca este deja
                        in_coada[v[nod][k].y]=true;
                        C.push(v[nod][k].y);
                    }
                }
            }
        }
    }
    if (ciclunegativ) {
        g<<"Ciclu negativ!";
    }
    else {
        FOR (i,2,N) {
            g<<lung[i]<<' ';
        }
    }
    f.close();g.close();
    return 0;
}