#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int NMAX = 50000 , Infinit = 2000000000;

struct EdgeStruct{
    int u , v , cost;
};

vector< EdgeStruct >Edge;
int N,M;
int dp[NMAX+5];

void Read(){
    EdgeStruct temp;
    int u , v , cost;

    fin>>N>>M;
    for(int i = 0 ; i<M ; i++){
        fin>>u>>v>>cost;
        temp.u = u ; temp.v = v ; temp.cost = cost;

        Edge.push_back(temp);
    }

}

void BellmanFord(){
    for(int i = 1 ; i<=N ; i++){
        dp[i] = Infinit;
    }
    dp[1] = 0;
    int u , v , cost;

    for(int i = 1 ; i<= N ; i++){
        for(int j = 0 ; j<M ; j++){
            u = Edge[j].u ; v = Edge[j].v ; cost = Edge[j].cost;
            if(dp[u]!=Infinit && dp[u]+cost < dp[v])
                dp[v] = dp[u]+cost;
        }
    }

    for(int i = 0 ; i<M ; i++){
        u = Edge[i].u ; v = Edge[i].v ; cost = Edge[i].cost;
        if(dp[u] != Infinit && dp[u]+cost<dp[v]){
            fout<<"Ciclu negativ!\n";
            return ;
        }
    }
    for(int i =2; i<=N ; i++){
        fout<<dp[i]<<' ';
    }
}
int main()
{
    Read();
    BellmanFord();
    return 0;
}