//BermanFloyd

#include<iostream>
#include<fstream>
#define infinit 10000
using namespace std;
void citire(int a[100][100],int &n)
{int m,i,x,y,j,z;
ifstream f("bellmanford.in");
f>>n>>m;
for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if (i==j)
        a[i][j]=0;
    else a[i][j]=infinit;

for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=z;
    }
f.close();
}
int BellmanFord(int a[100][100],int n,int x,int pred[100],int d[100])
{int i,j,k,ok;
    for (i=1;i<=n;i++)
        {
            pred[i]=0;
            d[i]=infinit;
        }
    d[x]=0;
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    for (k=1;k<=n;k++)
        if (d[j]!=infinit && a[i][j]!=infinit)
            if (d[k]>d[j]+a[j][k])
                {
                    d[k]=d[j]+a[j][k];
                    pred[k]=j;
                }

    for (j=1;j<=n;j++)
    for (k=1;k<=n;k++)
        if (d[k]>d[j]+a[j][k])
            return 0;

        return 1;
}
/*void afisare(int a[100][100],int n)
{for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        cout<<a[i][j]<<"   ";
        cout<<'\n';
    }
}*/
int main()
{
int a[100][100],n,i,pred[100],d[100],x;
ofstream g("bellmanford.out");

citire(a,n);
if (BellmanFord(a,n,1,pred,d))
    for (i=1;i<=n;i++)
        g<<d[i]<<" ";
    else
        g<<"Ciclu negativ";
        g.close();
}

//http://www.infoarena.ro/problema/lanterna
//http://www.infoarena.ro/problema/ciclu





//vector de muchii
/*
#include<iostream>
#include<fstream>
#define infinit 10000
using namespace std;
struct muchie{int x,y,c;};
muchie me[infinit];
int n,m,pred[100],d[100];
void citire()
{int i,x,y,c;
ifstream f("bellmanford.in");
f>>n>>m;
    for (int i=1;i<=m;i++)
        f>>me[i].x>>me[i].y>>me[i].c;
   f.close();
}
int BellmanFord(int x0)
{int i,j,k;
for (i=1;i<=n;i++)
    {
        pred[i]=0;
        d[i]=infinit;
    }
d[x0]=0;
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
        if (d[me[j].y]>d[me[j].x]+me[j].c)
            {
                d[me[j].y]=d[me[j].x]+me[j].c;
                pred[me[j].y]=me[j].x;
            }
    for (j=1;j<=m;j++)
         if (d[me[j].y]>d[me[j].x]+me[j].c)
            return 0;
return 1;

}
int main()
{int i,x,y,c,x0;
citire();
for (int i=1;i<=n;i++)
    if (BellmanFord(1))
            cout<<d[i]<<" ";
    else
            cout<<"Ciclu negativ";

}
*/
//arbore=graf conex fara cicluri