#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
typedef struct edge{
    int first, second, weight;
}edge;

using namespace std;

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

void BellmanFord(int n, vector<edge> E, int source, vector<int>& distance, vector<int>& predecessor)
{
    for(int i = 0; i <= n; i++)
        distance.push_back(INT_MAX),predecessor.push_back(0);

    distance.at(source) = 0;

    for(int i = 1; i <= n; i++)
    {
        for(unsigned int j = 0; j < E.size(); j++)
        {
            if(distance.at(E[j].first) + E[j].weight < distance.at(E[j].second))
            {
                distance.at(E[j].second) = distance.at(E[j].first) + E[j].weight;
                predecessor.at(E[j].second) = E[j].first;
            }
        }
    }

    for(unsigned int j = 0; j < E.size(); j++)
        if(distance.at(E[j].first) + E[j].weight < distance.at(E[j].second))
            {
                g << "Ciclu negativ!";
                return;
            }
}

int main()
{
    int n, m, a, b, w;
    f >> n >> m;
    vector<edge> E;
    vector<int> distance, predecessor;
    for(int i = 0; i < m; i++)
    {
        f >> a >> b >> w;
        edge n;
        n.first = a;
        n.second = b;
        n.weight = w;
        E.push_back(n);
    }

    BellmanFord(n, E, 1, distance, predecessor);

    for(int i = 1; i < n; i++)
    {
        cout << "De la nodul 1 la nodul " << i+1 <<" este distanta " << distance[i+1];
        cout<<endl;
    }
    return 0;
}