#include <fstream>
#include <queue>
#include <bitset>

using namespace std;

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

const int NMAX = 50005, INF = (1 << 30);
int n, m, x, y, c;
vector < vector < pair < int, int > > > v;
vector <int> D;

bool spfa(int start)
{
    D.assign(n + 1, INF);
    vector <int> frec(n + 1,0);

    queue<int>q;
    bool inqueue[NMAX];

    D[start] = 0, q.push(start), inqueue[start] = 1;

    while(!q.empty())
    {
        int p = q.front();
        q.pop();
        inqueue[p] = 0;

        for(int i = 0 ; i < v[p].size() ; i++)
        {
            int to = v[p][i].first, len = v[p][i].second;

            if(D[p] + len < D[to])
            {

                D[to] = D[p] + len;
                if(!inqueue[to])
                {
                    q.push(to), inqueue[to] = 1, frec[to]++;

                    if(frec[to]>=n)
                        return 0;
                }

            }
        }
    }
    return 1;
}

void citire()
{
    cin >> n >> m;
    v.resize(n+5);
    for(int i=1; i<=m; i++)
        cin >> x >> y >> c,
        v[x].emplace_back(y,c);

}

int main()
{
    citire();

    bool ans=spfa(1);

    if(ans == 0)
        cout << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            cout << D[i] << " ";

    return 0;
}