#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("bellmandford.in");
ofstream g("bellmandford.out");
struct muchie
{
    int x, y,c;
}M[250004];
int n, m;
void citire ()
{
    f>>n>>m;
    int i;
    for(i=1;i<=m;i++)
    {
        int x, y,c;
        f>>x>>y>>c;
        M[i].x=x;
        M[i].y=y;
        M[i].c=c;
    }
    f.close();
}
int main()
{
    citire();
    vector <int> costVechi(n+2);
    vector <int> costNou(n+2);
    costVechi[1]=0;
    costNou[1]=0;
    int i;
    for(i=2;i<=n;i++)
    {
        costVechi[i]=50000;
        costNou[i]=50000;
    }
    for(i=1;i<=n;i++)
    {
        int j;
        for(j=1;j<=m;j++)
            if(costVechi[M[j].x]+M[i].c<costNou[M[j].y])
                costNou[M[j].y]=costVechi[M[j].x]+M[j].c;
        costVechi=costNou;
    }
    vector <int> v(n+2);
    v=costNou;
    int j;
    for(j=1;j<=m;j++)
        if(costVechi[M[j].x]+M[j].c<costNou[M[j].y])
            costNou[M[j].y]=costVechi[M[j].x]+M[j].c;
    costVechi=costNou;
    for(i=2;i<=n;i++)
        g<<costNou[i]<<" ";
    if(costNou==v)
        cout<<"Nu exista cicluri negative.";
    else
        cout<<"Exista cicluri negative.";
    return 0;
}