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

const int N=50005,inf=1<<30;
int dist[N],use[N],n;
struct muchie{int catre,cost;};
vector<muchie> a[N];
queue<int> v;

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

void init()
{
    for (int i=1;i<=n;i++)
        dist[i]=inf;
}

bool BF(int x)
{
    init();
    dist[x]=0;
    v.push(x);
    while (!v.empty())
    {
        x=v.front();
        v.pop();
        use[x]++;
        if (use[x]==n)
            return false;
        for (vector<muchie>::iterator i=a[x].begin();i!=a[x].end();i++)
            if (dist[(*i).catre]>dist[x]+(*i).cost)
            {
                dist[(*i).catre]=dist[x]+(*i).cost;
                v.push((*i).catre);
            }
    }
    return true;
}

int main()
{
    int m,x,y,c;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y>>c;
        a[x].push_back((muchie){y,c});
    }
    if (BF(1))
        for (int i=2;i<=n;i++)
            out<<dist[i]<<" ";
    else
        out<<"Ciclu negativ!";
    out<<"\n";
    return 0;
}