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

using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
const int N = 50005;
const int INF = 500000000;

struct muchie
{
    int nod, cost;
};
vector <muchie> v[N];

bool eincoada[N];
int nrviz[N], d[N];

queue <int> coada;

int main()
{
    int n, m, i, x, y, val;
    in >> n >> m;
    for(i = 1; i <= m; i++)
    {
        in >> x >> y >> val;
        v[x].push_back( {y, val});
    }

    coada.push(1);
    eincoada[1] = true;
    nrviz[1] = 1;
    for(i = 2; i <= n; i++)
        d[i] = INF;
    int node;
    bool ok = true;
    while(!coada.empty() && ok == true)
    {
        node = coada.front();
        coada.pop();
        eincoada[node] = false;
        for(i = 0; i < v[node].size(); i++)
        {
            if(d[v[node][i].nod] > d[node] + v[node][i].cost)
            {

                d[v[node][i].nod] = d[node] + v[node][i].cost;
                if(eincoada[v[node][i].nod] == false)
                {
                    coada.push(v[node][i].nod);
                    eincoada[v[node][i].nod] = true;
                }
                nrviz[v[node][i].nod] ++;
                if(nrviz[v[node][i].nod] > n)
                {
                    out << "Ciclu negativ!";
                    return 0;
                }
            }

        }

    }
    for(i = 2; i <= n; i++)
    {
        if(d[i] == INF)
            d[i] = 0;
        out << d[i]<<" ";
    }
    return 0;
}