#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013

#define fs first
#define sc second

using namespace std;

typedef pair<int, int> pereche;

int n, m, i, x, y, z, nod, dst, nxt, val;
int d[50005], f[50005];

vector <pereche> v[50005];
vector <pereche> :: iterator it;

queue <int> q;

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

    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        v[x].push_back( {y,z} );
    }

    for(i = 2; i <= n; i++)
        d[i] = INF;

    q.push(1);
    while(!q.empty())
    {
        nod = q.front();
        q.pop();

        dst = d[nod];
        for(it = v[nod].begin(); it != v[nod].end(); it++)
        {
            nxt = (*it).fs;
            val = (*it).sc;
            if(d[nxt] > dst + val)
            {
                d[nxt] = dst + val;
                q.push(nxt);

                f[nxt]++;
                if(f[nxt] > n)
                {
                    puts("Ciclu negativ!");
                    return 0;
                }
            }
        }
    }

    for(i = 2; i <= n; i++)
        printf("%d ", (d[i] != INF ? d[i] : 0));
    return 0;
}