#include<bits/stdc++.h>
#define Inf 10000
using namespace std;
int n, c[Inf][Inf],d[Inf],pred[Inf],m;
struct muchie{int x,y,c;};
muchie me[Inf];
void citire()
 {  int m,i,j;
     ifstream fin("poveste.in");
     fin>>n>>m;
     for( i=1;i<=n;i++)
        for( j=1;j<=n;j++)
        if(i==j) c[i][j]=0;
        else c[i][j]=Inf;

     for(i=1;i<=m;i++)
     {int x,y,z;
         fin>>x>>y>>z;
         c[x][y]=z;
     }

}

void citire_1()
{
    int i,j;
     ifstream fin("bellmanford.in");
     fin>>n>>m;

     for(i=1;i<=m;i++)
     {int x,y,z;
         fin>>me[i].x>>me[i].y>>me[i].c;
     }

}

int bellman_ford_1(int S)
{
    int i,j;
    for(i=2;i<=n;i++) d[i]=Inf;
    d[S]=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(i=1;i<=m;i++)
       if(d[me[i].y]>d[me[i].x]+me[i].c)
       return 0;
    return 1;


}




int bellman_ford(int S)
{
     int i,j,k;
     for(i=1;i<=n;i++) {d[i]=Inf;
     pred[i]=S;
     }
     d[S]=0;

     for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          for(k=1;k<=n;k++)
             if(d[j]!=Inf && c[j][k]!=Inf && d[k]>d[j]+c[j][k])
             {
                 d[k]=d[j]+c[j][k];
                 pred[k]=j;
             }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(d[j]!=Inf && d[i]!=Inf && d[j]>d[i]+c[i][j]) return 0;

 return 1;
}

int main()
{  int x,i,S;
ofstream g("bellmanford.out");
    citire_1();
    //cin>>S;
    if(bellman_ford_1(1))
        for(i=2;i<=n;i++) g<<d[i]<<' ';
    else g<<"Ciclu negativ!";
    //cin>>x;
    //if(bellman_ford(x))
    //for(i=1;i<=n;i++) cout<<d[i]<<' ';
    //else cout<<"circuit negativ";
    //for(i=1;i<=m;i++) cout<<me[i].x<<' '<<me[i].y<<' '<<me[i].c<<endl;
    //t: ciclu si lanterna
}