#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 50005
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector <int> v[NMAX],val[NMAX];
queue <int> q;
int n,m,ok[NMAX],d[NMAX];
bool kk=1;

void bellmanford(int start)
{
    q.push(start);
    while(!q.empty() && kk)
    {
        int k=q.front();
        if(ok[k]>n) kk=0;
        q.pop();
        for(int i=0;i<v[k].size();i++)
        {
            int nr=v[k][i];
            if(!ok[nr] || val[k][i]+d[k]<d[nr])
            {
                ok[nr]++;
                d[nr]=val[k][i]+d[k];
                q.push(nr);
            }
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,nr;
        f>>x>>y>>nr;
        v[x].push_back(y);
        val[x].push_back(nr);
    }
    bellmanford(1);
    if(kk)
        for(int i=2;i<=n;i++) g<<d[i]<<" ";
    else g<<"Ciclu negativ!";
}