#include<fstream>
#include<queue>
#include<vector>
#define inf 2000000
#define dim 50002
using namespace std;
ifstream  f("bellmanford.in");
ofstream  g("bellmanford.out");
int D[dim],n,m,x,y,c,i,viz[dim],contor[dim];
vector<int>G[dim],C[dim];
queue<int>Q;
void bellman (){
    for(i=2;i<=n;i++)
        D[i]=inf;
    D[1]=0;
    Q.push(1);
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        viz[x]=0;
        for(int i=0;i<G[x].size();++i){

            if(D[G[x][i]]>D[x]+C[x][i]){
                D[G[x][i]]=D[x]+C[x][i];
                if(!viz[G[x][i]]){
                    if(contor[G[x][i]]>n){
                        g<<"Ciclu negativ!";
                        return ;
                    }
                    else{
                    viz[G[x][i]]=1;
                    ++contor[G[x][i]];
                    Q.push(G[x][i]);
                    }
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        g<<D[i]<<" ";
}
int main (){
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        G[x].push_back(y);
        C[x].push_back(c);
    }
    bellman();
    return 0;
}