#include <bits/stdc++.h>
#define nmax 50005
#define inf 1 << 30

using namespace std;

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

int n, m, d[nmax], cont_incoada[nmax];
vector<pair<int, int>> g[nmax];
bool incoada[nmax];

struct compara{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};

priority_queue<int, vector<int>, compara> q;

int main()
{
    fin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for(int i = 1; i <= n; ++i) d[i] = inf;
    d[1] = 0;
    q.push(1);
    incoada[1] = 1;
    bool ok = 1;
    while(!q.empty() && ok)
    {
        int node = q.top();
        int minvalue = node;
        q.pop();
        incoada[node] = 0;
        for(int i = 0; i < g[node].size(); ++i)
        {
            int next_node = g[node][i].first;
            int cost = g[node][i].second;
            if(d[node] + cost < d[next_node])
            {
                d[next_node] = d[node] + cost;
                if(!incoada[next_node])
                {
                    if(cont_incoada[next_node] > n)
                    {
                        ok = 0;
                    }
                    else{
                    q.push(next_node);
                    incoada[next_node] = 1;
                    ++cont_incoada[next_node];
                    }
                }
            }
        }
    }
    if(!ok)
    {
        fout << "Ciclu negativ!";
        return 0;
    }
    for(int i = 2; i <= n; ++i)
    {
        if(d[i] == inf) fout << 0 << " ";
        else fout << d[i] << " ";
    }
    return 0;
}