#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <set>

#define inf 200000000
#define N 500000

using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

vector <pair <int,int> > p[N];
queue <int> que;

bool b[N],cycle=false;

int n,m,i,j,from,to,cost,dist[N],fr[N];

int main()
{
    f>>n>>m;
    while(m)
    {
        f>>from>>to>>cost;
        p[from].push_back(make_pair(to,cost));
        m--;
    }
    for(i=1;i<=n;i++)
        dist[i]=inf;
    dist[1]=0;
    que.push(1);
    while(!que.empty())
    {
            int nod=que.front();
            b[nod]=0;
            que.pop();
            cout<<nod<<"\n";
            vector <pair < int,int> >::iterator it;
            for(it=p[nod].begin();it!=p[nod].end();it++)
            {
                to=it->first;
                cost=it->second;
                if(dist[to]>dist[nod]+cost)
                {
                    dist[to]=dist[nod]+cost;
                    if(b[to]==false)
                    {
                        b[to]=true;
                        que.push(to);
                        fr[to]++;
                    }
                    else
                    {
                        fr[to]++;
                    }
                    if(fr[to]>n)
                        cycle=true;
                }
            }
    }
    if(cycle==true)
        g<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;i++)
            g<<dist[i]<<' ';
    }

    return 0;
}