#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <climits>

#define INF INT_MAX
#define NMAX 50005
#define pb push_back
#define f first
#define s second

using namespace std;

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

int cnt[NMAX];
int d[NMAX];

bitset <NMAX> in_Q;
queue <int> Q;
vector < pair <int, int> > G[NMAX];
int main()
{
    int n, m;
    int x, y, c;

    fin >> n >> m;
    for (; m; --m)
    {
        fin >> x >> y >> c;
        G[x].pb({y, c});
    }

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

    Q.push(1); cnt[1] = 1; in_Q[1] = true;
    int nod;
    bool ncycle = false;
    while (!Q.empty() && !ncycle)
    {
        nod = Q.front();
        Q.pop();
        in_Q[nod] = false;

        for (vector < pair <int, int> > :: iterator it = G[nod].begin(); it != G[nod].end(); ++it)
            if (d[it -> f] > d[nod] + it -> s)
            {
                d[it -> f] = d[nod] + it -> s;
                if (!in_Q[it -> f])
                {
                    Q.push(it -> f);
                    in_Q[it -> f] = true;
                    ++cnt[it -> f];
                    if (cnt[it -> f] > n) ncycle = true;
                }
            }
    }
    if (ncycle) fout << "Ciclu negativ!\n";
    else for (int i = 2; i <= n; ++i)
        fout << d[i] << ' ';

    return 0;
}