#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;


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

const int DIM = 250005;
const int oo = (1 << 31) - 1;

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

int d[DIM];

int n,m;

priority_queue <int, vector <int> > c;

bool viz[DIM];

void bellmanford(int &k)
{

    for(int i = 1;i <= n;i++)
    viz[i] = false;

    c.push(1);
    while(!c.empty())
    {
        int nod = c.top();
        c.pop();
        viz[nod] = true;

        for(int i = 0;i < v[nod].size() ;i++)
        {
            int cost = v[nod][i].second;
            int vec = v[nod][i].first;

            if(d[nod] + cost < d[vec])
            {
                k++;
                d[vec] = d[nod] + cost;
                if(viz[vec] == false)
                c.push(vec);
            }
        }
    }


}
int main()
{

   in >> n >> m;

   for(int i = 1; i <= m; i++)
   {
        int x, y, c;

        in >> x >> y >> c;

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

   for(int i = 1;i <= n; i++)
    d[i] = oo;

    d[1] = 0;
   for(int i = 1;i <= n - 1;i++)
   {
       int k = 0;
       bellmanford(k);
       if(k == 0)
       {
           for(int j = 2;j <= n;j++)
            out << d[j] <<" ";
           return 0;
       }
       if(k != 0 && i == n - 1)
       {
           int k = 0;
           bellmanford(k);
           if(k!=0)
            out << "Ciclu negativ!";
           else
              {
           for(int j = 2;j <= n;j++)
            out << d[j] <<" ";
            return 0;
                }
       }
   }

      return 0;
}