#include <iostream>
#include <bits/stdc++.h>
#define inf 2000
using namespace std;

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

int dist[260000];

vector < list < pair <int,int> > > V;
queue < int > Q;

int main()
{
    int n,m,x,y,z;
    fin >> n >> m;
    V.resize(m);
    for (int i = 0 ; i < m; i++)
    {
        fin >> x >> y >> z;
        V[x].push_back({y,z});
    }
    for (int i = 1 ; i <= n; i++)
        dist[i] = inf;

    bool circuit = false;
    vector <bool> in_coada(n+1);
    vector <int> nr_apar(n+1);

    dist[1] = 0;
    Q.push(1);
    while(!Q.empty() && !circuit)
    {
        int x = Q.front();
        Q.pop();
        in_coada[x] = false;
        for (auto a:V[x])
       // if (dist[x] < inf)
        if(dist[x] + a.second < dist[a.first])
        {
            dist[a.first] = dist[x] + a.second;
            cout << a.first << " " << dist[a.first] << " " << in_coada[a.first] << " ";
            if (!in_coada[a.first])
                {
                    if (nr_apar[a.first] > n)
                        circuit = true;

                    else
                    {
                        Q.push(a.first);
                        in_coada[a.first] = true;
                        nr_apar[a.first]++;

                    }
                }
            cout << in_coada[a.first] << endl;
        }
    /*for (int i = 1; i<=n; i++)
        cout << dist[i] << " ";
    cout << "\n";*/
    }
    if (circuit)
        fout << "Ciclu negativ!";
    else for (int i = 2; i <= n; i++)
            fout << dist[i] << " ";

    return 0;
}