#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
const int N = 50001;
const int VMAX_PUNCT = 1001;
const int VMAX_TOTAL = N*VMAX_PUNCT;
int n , m;
queue <int> coada;
int nrTreceri[N];
int cost[N];
struct muchie{int vecin,cost;};
muchie makeMuchie(int a,int b){muchie x;x.vecin=a;x.cost=b;return x;}
vector <muchie> muchii[N];
bool bfs(){
    coada.push(1);
    nrTreceri[1]=1;
    cost[1]=0;
    while(!coada.empty()){
        int old_varf = coada.front();
        int old_cost = cost[old_varf];
        coada.pop();
        for(int i=0;i<muchii[old_varf].size();i++){
            int new_varf = muchii[old_varf][i].vecin;
            int new_cost = muchii[old_varf][i].cost;
            if(cost[new_varf] > new_cost + old_cost){
                nrTreceri[new_varf]++;
                if(nrTreceri[new_varf]==n){
                    return false;
                }
                coada.push(new_varf);
                cost[new_varf] = new_cost + old_cost;
            }
        }
    }
    return true;
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,cost;
        in>>x>>y>>cost;
        muchii[x].push_back(makeMuchie(y,cost));
    }
    for(int i=1;i<=n;i++){
        cost[i]=VMAX_TOTAL;
    }
    if(bfs()==false){
        out<<"Ciclu Negativ";
    } else {
        for(int i=2;i<=n;i++){
            out<<cost[i]<<" ";
        }
    }
    return 0;
}