#include <bits/stdc++.h>
using namespace std;

#define lsize(x) la[x].v.size()
#define to(x,i) la[x].v[i].first
#define cost(x,i) la[x].v[i].second
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int N=5e4+5,M=2534+5,INF=1000000000;
int dist[N];
struct graf
{
    vector<pair<int,int> > v;
    int parcurs;
}la[N];

bool bford(int n)
{
    for(int i=2;i<=n;i++) dist[i]=INF;
    dist[1]=0;

    for(int l=1;l<n;l++)
    {
        queue <pair<int,int> > q;
        q.push(make_pair(1,0)); //nod, cost

        while(!q.empty())
        {
            int nod=q.front().first;
            int d=q.front().second;

            for(int i=0;i<lsize(nod);i++)
            {
                int to=to(nod,i);
                int cost=cost(nod,i);

                if(la[to].parcurs!=l && d+cost < dist[to])
                {
                    dist[to]=d+cost;
                    la[to].parcurs=l;
                    q.push(make_pair(to,dist[to]));
                }
            }
            q.pop();
        }
    }

    queue <pair<int,int> > q;
        q.push(make_pair(1,0)); //nod, cost

        while(!q.empty())
        {
            int nod=q.front().first;
            int d=q.front().second;

            for(int i=0;i<lsize(nod);i++)
            {
                int to=to(nod,i);
                int cost=cost(nod,i);

                if(d+cost < dist[to])
                {
                    return 1;
                }
                    q.push(make_pair(to,dist[to]));
            }
            q.pop();
        }
    return 0;
}

int main()
{
    int n,m;
    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int from,to,cost;
        in>>from>>to>>cost;
        la[from].v.push_back(make_pair(to,cost));
    }

    if(bford(n))
    {
        out<<"Ciclu negativ!";
        return 0;
    }

    for(int i=2; i<=n; i++)
        out<<dist[i]<<' ';

    return 0;
}