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

#define INF 1000000000
#define NMAX 50001

using namespace std;

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

int n, x0=1;

vector<pair<int, int>> G[NMAX];
queue<int> C;

int dmin[NMAX], nr[NMAX];
bool negativ;

void bellman_ford();
int main()
{
    int i, m, x, y, c;
    cin >> n >>  m ;
    for (int i = 1;i <= m;i++)
    {
        cin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    bellman_ford();

    if (negativ) cout << "Ciclu negativ!";
    else
    {
        for (int i = 1;i <= n;i++)
        {
            if (i != x0)
            {
                cout << (dmin[i] != INF ? dmin[i] : 0)<<" ";
            }
           
        }
    }
}

void bellman_ford()
{
    vector<pair<int, int>> ::iterator it;
    int i, x;
    for (i = 1;i <= n;++i) dmin[i] = INF;
    dmin[x0] = 0;
    C.push(x0);
    while (!C.empty() && !negativ)
    {
        x = C.front();
        C.pop();
        for (it = G[x].begin();it != G[x].end();++it)
        {
            if (dmin[it->first] > dmin[x] + it->second)
            {
                dmin[it->first] = dmin[x] + it->second;
                nr[it->first]++;
                C.push(it->first);
                if (nr[it->first] > n) negativ = true;
            }

        }
    }
}