#include <iostream>
#include <fstream>

using namespace std;

const int INF = 60000;
int n,m,d[100],c[100][100],tata[100];

int bf(int x0)
{
   int ok, i, j, k;
   for (i=1;i<=n;i++) {
      tata[i] = 0; d[i] = INF;
      }
   d[x0] = 0;
   for (i=1; i<=n; i++)
   {
      ok = 0;
      for (j=1;j<=n;j++)
         for (k=1;k<=n;k++)
            if (d[j]!=INF && c[j][k]!=INF)
               if (d[k]>d[j]+c[j][k])
               {
                  d[k] = d[j]+c[j][k];
                  tata[k] = j;
                  ok = 1;
               }
   }
   if (ok == 1) cout<<"Ciclu negativ!";
   return ok;
}

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    in>>n>>m;
    int x,y,tt;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>tt;
        c[x][y] = tt;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j && c[i][j]==0)
                c[i][j] = INF;

    bf(1);


    for(int i=2; i<=n; i++)
        out<<d[i]<<" ";
}