#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

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

const int N = 50005;
const int INF = 1e9;

int n, m, a, b, c, dist[N], viz[N], f[N];

struct graf
{
    int nod, cost;
};

vector < graf > g[N];

struct cmp
{
    bool operator()(graf a, graf b)
    {
        return a.cost > b.cost;
    }
};

priority_queue < graf, vector < graf >, cmp > q;

void bellmanford(int s)
{
    for (int i = 1; i <= n; ++i)
        dist[i] = INF;
    dist[s] = 0;
    q.push({s, 0});
    viz[s] = 1;
    ++f[s];
    while(!q.empty() && f[q.top().nod] < n)
    {
        int u = q.top().nod;
        viz[u] = 0;
        q.pop();
        for(int j = 0; j < g[u].size(); ++j)
        {
            int v = g[u][j].nod;
            int duv = g[u][j].cost;
            if(dist[u] + duv < dist[v])
            {
                dist[v] = dist[u] + duv;
                ++f[v];
                if(!viz[v])
                {
                    q.push({v, dist[v]});
                    viz[v] = 1;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while(cin >> a >> b >> c)
    {
        g[a].push_back({b, c});

    }
    bellmanford(1);
    if (!q.empty())
    {
        cout << "Ciclu negativ!";
    }
    else
    {
        for(int i = 2; i <= n; ++i)
        {
            if(dist[i] == INF)
                cout << "-1 ";
            else
                cout << dist[i] << ' ';
        }
    }

    return 0;
}