#include <fstream>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,d[50001],iq[50001],viz[50001];
#define INF 1000000000
vector <pair<int,int>>G[50001];
int main(){
    fin>>n>>m;
    for(int ll=1;ll<=m;ll++){
        int i,j,cost;
        fin>>i>>j>>cost;
        G[i].push_back({j,cost});
    }
    for(int i=2;i<=n;i++)
        d[i]=INF;
    viz[1]=1;

    queue<int>Q;
    Q.push(1); int ok=1;
    while(!Q.empty()){
            if(ok==0)
                break;
        int front=Q.front();Q.pop();
        viz[front]=0;
        iq[front]++;
        if(iq[front]>n){
            ok=0; break;
        }
        for(size_t i=0;i<G[front].size();i++){
            int vecin=G[front][i].first;
            int cost=G[front][i].second;
            if(d[vecin]>cost+d[front]){
                d[vecin]=cost+d[front];
            if(viz[vecin]==0)
                Q.push(vecin);
                viz[vecin]=1;
            }
        }
    }
    if(ok==0)
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<d[i]<<" ";
    return 0;
}