#include <fstream>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define infinit 2000000000
struct muchie
{ int a,b,c;

};
int cost_vechi[50001];
int cost_nou[50001];
int copie[50001];
muchie mm[250001];
int n,m;
int main()
{ fin>>n>>m;
  for(int i=1;i<=m;i++)
    fin>>mm[i].a>>mm[i].b>>mm[i].c;

for(int i=2;i<=n;i++)
    cost_vechi[i]=cost_nou[i]=infinit;

    for(int j=1;j<=n;j++)
       {for(int i=1;i<=m;i++)
        if(cost_vechi[mm[i].a]+mm[i].c<cost_nou[mm[i].b])
        cost_nou[mm[i].b]=cost_vechi[mm[i].a]+mm[i].c;

        for(int i=2;i<=n;i++)
           cost_vechi[i]=cost_nou[i];
       }
   for(int i=2;i<=n;i++)
           copie[i]=cost_vechi[i];
   for(int i=1;i<=m;i++)
        if(cost_vechi[mm[i].a]+mm[i].c<cost_nou[mm[i].b])
        cost_nou[mm[i].b]=cost_vechi[mm[i].a]+mm[i].c;

     int ok=1;
     for(int i=2;i<=n;i++)
     if(copie[i]!=cost_nou[i]) {fout<<"Ciclu negativ!";return 0;}

    for(int i=2;i<=n;i++)
    fout<<cost_nou[i]<<" ";
    return 0;
}