//
//  A.cpp
//
//  Created by Vlad Turcuman on 24/09/2017.
//  Copyright © 2017 Vlad Turcuman. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>

#define pii pair<int,int>
#define fs first
#define sc second
#define NMax 1001
#define Mod 1000000007
#define oo 2000000000


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


int n;
struct Edge{
    int node1,node2,cost;
};

vector<Edge> edges;
int Min[50010];

void BellmanFord()
{
    for(int i=2;i<=n;i++)
        Min [i] = oo;
    Min[1] = 0;
    
    for(int i=1;i<n;i++)
    {
        for(int j = 0;j<edges.size();j++)
            if(Min[edges[j].node1] + edges[j].cost < Min[edges[j].node2])
                Min[edges[j].node2] = Min[edges[j].node1] + edges[j].cost;
    }
    
    
    for(int j = 0;j<edges.size();j++)
        if(Min[edges[j].node1] + edges[j].cost < Min[edges[j].node2])
        {
            fout<<"Ciclu negativ!";
            return;
        }
    
    for(int i=2;i<=n;i++)
        fout<<Min[i]<<' ';
    
}

int main()
{
    int m,node1,node2,cost;
    fin>>n>>m;
    
    for(int i=1;i<=m;i++)
    {
        fin >> node1 >> node2 >> cost;
        edges.push_back({node1, node2, cost});
    }
    
    BellmanFord();
    
    return 0;
}