#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 50001;
vector<int> G[Nmax],C[Nmax];
int D[Nmax],inq[Nmax],N,M;
queue<int> q;
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y,c; in>>x>>y>>c;
        G[x].push_back(y);
        C[x].push_back(c);
    }
    for(int i=2;i<=N;i++) D[i]=INF;
    q.push(1); inq[1]=1;
    while(!q.empty()){
        int x=q.front(); q.pop(); inq[x]=-inq[x];
        for(int i=0;i<G[x].size();i++){
            if(D[x]+C[x][i] < D[G[x][i]]){
                D[G[x][i]]=D[x]+C[x][i];
                if(inq[G[x][i]]<1){
                    if(inq[G[x][i]]<-M){
                        out<<"Ciclu negativ!\n";
                        return 0;
                    }
                    q.push(G[x][i]);
                    inq[G[x][i]]=1-inq[G[x][i]];
                }
            }
        }
    }
    for(int i=2;i<=N;i++) out<<D[i]<<' ';
    return 0;
}