#include <fstream>
#include <queue>
#include <vector>
#define mp make_pair
#define fi first
#define se second
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int x,y,c,i,cost,n,m,bag[1<<16],d[1<<16],inQ[1<<16];
vector < pair<int,int> > v[1<<16];
queue <int> Q;
void bellmanford()
{
    for(i=2;i<=n;++i) d[i]=1<<30;
    Q.push(1);
    bag[1]++;
    inQ[1]=1;
    while(!Q.empty())
    {
        int nod=Q.front();
        inQ[nod]=0;
        for(vector < pair<int,int> > :: iterator it=v[nod].begin();it!=v[nod].end();++it)
        if(d[nod]+it->se <d[it->fi])
        {
            d[it->fi]=d[nod]+it->se;
            if(!inQ[it->fi])
            {
                inQ[it->fi]=1;
                Q.push(it->fi);
            }
            bag[it->fi]++;
            if(bag[it->fi]==n)
            {
                cost=1;
                return;
            }
        }
        Q.pop();
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        v[x].push_back(mp(y,c));
    }
    bellmanford();
    if(cost) g<<"Ciclu negativ!";
    else for(i=2;i<=n;++i) g<<d[i]<<" ";
    return 0;
}