#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#include <cassert>

using namespace std;
#define MAXN 50001
#define INF 1999999999
struct nod {
    int urm;
    int cost;
};

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

int n,m,i,j,a;
nod aux;
vector<nod> vecini[MAXN];
int cost[MAXN],apar[MAXN];
bitset<MAXN> inq;
queue<int> q;

bool bellmanford() {
    while (!q.empty()) {
        a=q.front();
        //cout<<"a="<<a<<"\n";
        q.pop();
        apar[a]++;
        inq[a]=0;
        if (apar[a]>n) return false;
        for(i=0;i<vecini[a].size();i++) {
            //cout<<"         "<<vecini[a][i].urm<<"("<<vecini[a][i].cost<<")\n";
            if (cost[vecini[a][i].urm]>cost[a]+vecini[a][i].cost) {
                cost[vecini[a][i].urm]=cost[a]+vecini[a][i].cost;
                if (!inq[vecini[a][i].urm]) {
                    inq[vecini[a][i].urm]=1;
                    q.push(vecini[a][i].urm);
                }
            }
        }
    }
    return true;
}

int main()
{
    fin>>n>>m;
    for(i=2;i<=n;i++) cost[i]=INF;
    apar[1]=1; cost[1]=0;
    for(i=0;i<m;i++) {
        fin>>a>>aux.urm>>aux.cost;
        vecini[a].push_back(aux);
    }
    q.push(1);
    if (bellmanford()) {
        for(i=2;i<=n;i++) {
            fout<<cost[i]<<" ";
        }
    }
    else fout<<"Ciclu negativ!\n";
    fout.close();
    return 0;
}