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

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

int n, m, a, b, dist[50001], c, vis[50001], inf = 999999;
bool inQ[50001], NC;
vector<int> AD[50001], C[50001];
queue<int> q;

void Bellmanford(int src)
{
    q.push(src);
    inQ[src] = 1;
    dist[src] = 0;
    vis[src] = 1;

    while (q.size() != 0 && NC != 1)
    {
        int nod = q.front();
        q.pop();
        inQ[nod] = 0;

        cout << nod << "\n";

        for (int i = 0; i < AD[nod].size(); i++)
        {
            int w = AD[nod][i];
            int c = C[nod][i];

            if (dist[w] > dist[nod] + c)
            {
                dist[w] = dist[nod] + c;
                vis[w]++;
                cout << w << " ";

                if (vis[w] > n)
                    NC = 1;

                if (inQ[w] == 0)
                {
                    inQ[w] = 1;
                    q.push(w);
                }
            }
        }
    }
}
int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> a >> b>> c;
        C[a].push_back(c);
        AD[a].push_back(b);
    }
    for (int i = 1; i <= n; i++)
        dist[i] = inf;

    Bellmanford(1);

    if (NC == 1)
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++)
            fout << dist[i] << " ";

    return 0;
}