#include <fstream>
#include <vector>
#define inf 200000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct muchie
{
    int a,b,cost;
};
vector<muchie>v;
int n,m;
void Read()
{
    fin>>n>>m;
    int i;
    muchie mc;
    for(i=0;i<m;++i)
    {
        fin>>mc.a>>mc.b>>mc.cost;
        v.push_back(mc);
    }
}
void BellmanFord()
{
    vector<int>cost_vechi(n+2);
    vector<int>cost_nou(n+2);
    int i,j;
    cost_vechi[1]=0;
    for(i=2;i<=n;++i)cost_vechi[i]=inf;
    cost_nou=cost_vechi;
    for(i=1;i<=n;++i)
    {
        for(j=0;j<m;++j)
            if(cost_vechi[v[j].a]+v[j].cost<cost_nou[v[j].b])
                cost_nou[v[j].b]=cost_vechi[v[j].a]+v[j].cost;
        cost_vechi=cost_nou;
    }
    for(j=0;j<m;++j)
        if(cost_vechi[v[j].a]+v[j].cost<cost_nou[v[j].b])
            cost_nou[v[j].b]=cost_vechi[v[j].a]+v[j].cost;
    if(cost_nou==cost_vechi)
    {
        for(i=2;i<=n;++i)fout<<cost_nou[i]<<" ";
    }
    else fout<<"Ciclu negativ!\n";
}
int main()
{
    Read();
    BellmanFord();
    return 0;
}