//presupunem ca nodul de start este 1. se poate adapta usor algoritmul pentru orice nod de start, tb doar citit
#include <iostream>
#include <fstream>
using namespace std;
const int inf=100000;
int n,m,d[101];
struct muchie{
    int ex1,ex2,L;
}x[10000];
void citire()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>x[i].ex1>>x[i].ex2>>x[i].L;
}

void init(int start)
{
    for(int i=1;i<=n;i++)
        d[i]=inf;
    d[start]=0;
}
void bellmanford(int start)
{
    bool CN=false;
    ofstream g("bellmanford.out");
    init(start);
    for(int j=1;j<n;j++)
    {
        for(int i=1;i<=m;i++)
        {
        if(d[x[i].ex2]>d[x[i].ex1]+x[i].L)
            {
                d[x[i].ex2]=d[x[i].ex1]+x[i].L;

            }

        for(int i=1;i<=n;i++)
        cout<<d[i]<<" ";
        cout<<endl;

        }
    }

    for(int i=1;i<=m&&CN==false;i++)
        if(d[x[i].ex2]>d[x[i].ex1]+x[i].L)
            CN=true;
    if(CN==true)
        g<<"Ciclu negativ!";
   else
        for(int i=2;i<=n;i++)
        g<<d[i]<<" ";
}
int main()
{
    citire();
    bellmanford(1);
    return 0;
}