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

#define max 1000000

using namespace std;

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

vector <pair<int, int>> a[50005];
int dist[50005], viz[50005];
queue <int> Q;

int main()
{
    int n, m;
    int x, y, c;
    fin>>n>>m;
    for (int i = 0; i < m; i++)
    {
        fin>>x>>y>>c;
        a[x].push_back({y, c});
    }
    for (int i = 2; i <= n; i++)
        dist[i] = max;

    Q.push(1);

    while (!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        if (viz[nod] >= n)
        {
            fout<<"Ciclu negativ!";
            return 0;
        }
        viz[nod]++;
        vector <pair<int, int>>::iterator it;
        for (it = a[nod].begin(); it != a[nod].end(); it++)
        {
            if (dist[it->first] > dist[nod] + it->second)
            {
                dist[it->first] = dist[nod] + it->second;
                Q.push(it->first);
            }
        }
    }

    for (int i = 2; i <=n; i++)
        fout<<dist[i]<<" ";

    return 0;
}