#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50000;

int N, M;
bool inQueue[NMAX + 5];
int cntQueue[NMAX + 5];
int dist[NMAX + 5];

struct elem
{
    int nod, cost;
};

vector<elem> g[NMAX + 5];
queue<elem> coada;

int main()
{
    fin >> N >> M;
    for(int i = 2; i <= N; i ++)
    {
        dist[i] = 1000000000;
    }
    while(M--)
    {
        int u, v, cost;
        fin >> u >> v >> cost;
        g[u].push_back({v, cost});
    }
    coada.push({1, 0});
    inQueue[1] = true;
    cntQueue[1] ++;
    while(!coada.empty())
    {
        int nod = coada.front().nod;
        int cost = dist[nod];
        coada.pop();
        inQueue[nod] = false;
        for(auto it : g[nod])
        {
            if(cost + it.cost < dist[it.nod])
            {
                dist[it.nod] = cost + it.cost;
                if(inQueue[it.nod] == false)
                {
                    inQueue[it.nod] = true;
                    cntQueue[it.nod] ++;
                    coada.push({it.nod, dist[it.nod]});
                    if(cntQueue[it.nod] == N)
                    {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i = 2; i <= N; i ++)
    {
        fout << dist[i] << ' ';
    }
    return 0;
}