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

using namespace std;

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

int n, m, ok;
const int nmax = 50005, val_mare = 50000000;
vector<pair<int, int> > list_vec[nmax];

int dist[nmax];
struct muchie
{
    int u, v, c;
};
muchie MC[250005];

void bellman()
{
    int i, j;

    for(i = 2; i <= n; ++i)
        dist[i] = val_mare;
    //dist[start] = 0;

    for(i = 1; i < n; ++i)
    {
        ok = 0;
        for(j = 1; j <= m; ++j)
        {
            if(dist[MC[j].v] > dist[MC[j].u] + MC[j].c)
            {
                ok = 1;
                dist[MC[j].v] = dist[MC[j].u] + MC[j].c;
            }
        }
        if(!ok)
        {
            for(int w = 2; w <= n; ++w)
                fout<<dist[w]<<' ';
        }
    }

    for(j = 1; j <= m; ++j)
    {
        if(dist[MC[j].v] > dist[MC[j].u] + MC[j].c)
        {
            fout<<"Ciclu negativ!";
            return;
        }
    }

    for(i = 2; i <= n; ++i)
        fout<<dist[i]<<' ';
}
int main()
{
    int u, v, c, i;
    fin>>n>>m;

    for(i = 1; i <= m; ++i)
        fin>>MC[i].u>>MC[i].v>>MC[i].c;

    bellman();

    return 0;
}