#include <fstream>
#include <iostream>
#include <vector>
#define s first
#define cost second
#include <queue>

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

vector <pair < int, int> > v[50010];
queue <int> cd;

int dist[50010], viz[50010];

int main ()
{
    int x, y, z, n, m, ok=0;
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for (int i=1; i<=n; i++)
        dist[i] = 999999999;
    cd.push(1);
    dist[1] = 0;
    while (!cd.empty() && !ok)
    {
        cout << cd.front() << ' ';
        for (auto it : v[cd.front()])
        {
            if (dist[cd.front()]+it.cost < dist[it.s])
            {
                cd.push(it.s);
                dist[it.s] = dist[cd.front()]+it.cost;
                viz[it.s] ++;
                if (viz[it.s]>n)
                    ok = 1;
            }
            
        }
        cd.pop();
    }
    if (ok==1)
        fout << "Ciclu negativ!";
    else
        for (int i=2; i<=n; i++)
            fout << dist[i] << ' ';
    
}