#include <iostream>
#include <fstream>
#include <queue>

#define pb push_back
#define fi first
#define se second
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
const int Nmax=50000, inf=2e9;
typedef pair<int, int> pii;

vector<pii> ad[Nmax];
int d[Nmax];

int n, m;
bool spfa(){
    for (int i=0; i<n; i++)
        d[i]=inf;
    vector<int> fr(n, 0);
    vector<bool> inqueue(n, 0);
    queue<int> q;

    q.push(0);
    d[0]=0;
    inqueue[0]=1;
    while (!q.empty()){
        int crt=q.front();
        q.pop();
        inqueue[crt]=0;

        for (auto it:ad[crt]){
            int pos=it.fi;
            int val=it.se;
            if (d[crt]+val<d[pos]){
                d[pos]=d[crt]+val;
                if (!inqueue[pos]){
                    q.push(pos);
                    inqueue[pos]=1;
                    fr[pos]++;
                    if (fr[pos]>n)
                        return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    fin>>n>>m;
    int a, b, c;
    for (int i=0; i<m; i++){
        fin>>a>>b>>c;
        a--; b--;
        ad[a].pb({b, c});
    }

    if (spfa())
        for (int i=1; i<n; i++)
            fout<<d[i]<<' ';
    else fout<<"Ciclu negativ!";

    return 0;
}