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

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

#define MAXN 50005
#define INF 0x3f3f3f3f
struct rct
{
    int nod,cost;
}act;

vector<rct> graf[MAXN];
queue<int> coada;
int cost[MAXN], nrc[MAXN];
int n,m,i,j,x,y,z,nod;
bool negativ;

int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        act.nod = y; act.cost = z;
        graf[x].push_back(act);
    }
    for(i=2; i<=n; i++)
        cost[i]=INF;

    coada.push(1); cost[1]=0;
    while(!coada.empty())
    {
        nod=coada.front(); coada.pop();
        for(i=0; i<graf[nod].size(); i++)
            if( cost[ graf[nod][i].nod ] > cost[nod] + graf[nod][i].cost )
            {
               if(nrc[ graf[nod][i].nod ] > n)
                    negativ = true;
               else
               {
                   nrc[ graf[nod][i].nod ]++;
                   cost[ graf[nod][i].nod ] = cost[nod] + graf[nod][i].cost;
                    coada.push( graf[nod][i].nod );
               }
            }
    }
    if(negativ)
        cout<<"Ciclu negativ!";
    else
        for(i=2; i<=n; i++)
            cout<<cost[i]<<" ";

    return 0;
}