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

using namespace std;

int N, M, i, j;

vector<pair<int, int> > V[50005];

bool ciclu_neg = false;

int DMIN[50005];

bool inQ[50005];

int solve()
{

    queue<int> Q;

    memset(inQ, false, sizeof(inQ));
    memset(DMIN, 0x3f3f3f3f, sizeof(DMIN));

    Q.push(1);
    DMIN[1] = 0;
    inQ[1] = true;
    vector<int> cInQ(50005, 0);

    while(!Q.empty() && !ciclu_neg)
    {
        int now = Q.front();
        Q.pop();
        inQ[now] = false;

        for(vector<pair<int, int> >::iterator it=V[now].begin();it!=V[now].end();++it)
            if(DMIN[now] < 0x3f3f3f3f && it->second + DMIN[now] < DMIN[it->first])
            {
                DMIN[it->first] = it->second + DMIN[now];

                if(!inQ[it->first])
                {

                    if(cInQ[it->first] > N)
                        ciclu_neg = true;
                    else
                    {
                        Q.push(it->first);
                        inQ[it->first] = true;
                        ++cInQ[it->first];
                    }
                }


            }

    }
}
int main()
{

   freopen("bellmanford.in", "r", stdin);
   freopen("bellmanford.out", "w", stdout);

    cin>>N>>M;

    for(i=1;i<=M;++i)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);

        V[A].push_back(make_pair(B, C));
    }

    solve();

    if(ciclu_neg)
        cout<<"Ciclu negativ!\n";
    else
        for(i=2;i<=N;++i)
            cout<<DMIN[i]<<" ";
   return 0;
}