#include <iostream>
#include<vector>
#include<queue>
#include<cstdio>

#define maxn 50073
#define infinit 1001 * maxn


using namespace std;

int cost[maxn],n,m,treceri[maxn];
bool viz[maxn];

typedef struct
{
 int nod;
 int cost;
}pereche;

vector <pereche> graf[maxn];

void inserare(int nod1,int nod2,int cost)
{
    pereche p;
    p.nod=nod2;
    p.cost=cost;

    graf[nod1].push_back(p);
}



int main()
{
    int x,y,c;

    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    cin>>n>>m;

    for (int i=1;i<=m;i++)
        {
            cin>>x>>y>>c;
            inserare(x,y,c);
        }

    fill(cost+1,cost+n+1,infinit);
    //fill(treceri+1,treceri+n+1,0);

    queue <int> coada;

    coada.push(1);
    treceri[1]++;
    cost[1]=0;
    bool ciclu = false;
    while (!coada.empty() && !ciclu)
    {
        int nod=coada.front();
        coada.pop();
        viz[nod]=false;
        int size = graf[nod].size();

        for (int i=0;i<size;i++)
        {
            int next = graf[nod][i].nod;
            if (cost[next]>graf[nod][i].cost+cost[nod])
            {
                   cost[next]=graf[nod][i].cost+cost[nod];
                   if (!viz[next])
                   {
                       if (treceri[next] > n)
                       {
                           ciclu = true;
                       }
                       else
                       {
                           coada.push(next);
                           viz[next]=true;
                           treceri[next]++;
                       }
                   }
            }
        }
    }
    if (ciclu)
    {
        cout << "Ciclu negativ!";
    }
    else
    {

        for (int i=2;i<=n;i++)
        cout<<cost[i]<<" ";
    }
    return 0;
}