#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;

queue <int > c;

int nr[DIM];

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

    d[1] = 0;

    c.push(1);
    nr[1] ++;
        int f = 0;
    while(!c.empty())
    {
        int nod = c.front();
        c.pop();
        for(int i = 0;i < v[nod].size(); i++)
        {
            int vec = v[nod][i].first;
            int cost = v[nod][i].second;

            if(d[nod] + cost < d[vec])
            {
                f = 0;
                d[vec] = d[nod] + cost;
                c.push(vec);
                nr[vec]++;
                if(nr[vec] == n)
                {
                    out <<"Ciclu negativ!";
                    return ;
                }
            }
            else
            f++;
        }
        if(f >= m)
        break;
    }

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

}

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));
   }

 bellmanford();



      return 0;
}