#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

#define lmax 50001
#define inf 50000001

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector <pair<int,int> >v[lmax];

queue <int> q;

bitset <lmax> ap;

int n,m,negativ;

int cost[lmax],nr[lmax];

inline void read()
{
    int x,y,z;

    f>>n>>m;

    for (int i=1;i<=m;i++)
     {

         f>>x>>y>>z;

         v[x].push_back(make_pair(y,z));
     }

     f.close();
}

inline void init()
{
    for (int i=2;i<=n;i++)
     cost[i]=inf;
}

inline void bellman_ford()
{
    q.push(1);
    ap[1]=1;

    while (!q.empty())
     {
        int x=q.front();   q.pop(); ap[x]=0;

        for (int i=0;i<v[x].size();i++)
          {
              int y=v[x][i].first;
              int c=v[x][i].second;

              if (cost[x]+c<cost[y])
               {
                   nr[y]++;

                   if (nr[y]==n)
                    {
                        negativ=1;
                        break;
                    }

                   cost[y]=cost[x]+c;

                   if (!ap[y])
                    {
                       q.push(y);
                       ap[y]=1;
                    }
               }
          }
          if (negativ)
           break;
     }
}

inline void write()
{
     if (negativ)

        g<<"Ciclu negativ!";

     else

        for (int i=2;i<=n;i++)
         g<<cost[i]<<" ";
}

int main()
{

    read();

    init();

    bellman_ford();

    write();

    g.close();
}