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

using namespace std;

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

const int MAXN = 50010;
const int INF = 0x3f3f3f3f;

vector < pair <int, int> > Graf[MAXN];
queue <int> Q;
int Best[MAXN], InQ[MAXN];
bool Viz[MAXN];

int main()
{
    int N, M, a, b, c, i;

    in >> N >> M;
    for (i = 1; i <= M; i ++){
        in >> a >> b >> c;

        Graf[a].push_back (make_pair (b, c));
    }

    memset (Best, 0x3f, sizeof (Best));
    Best[1] = 0;
    Q.push (1);

    int nod;
    vector < pair <int, int> > :: iterator it;

    while (!Q.empty ()){
        nod = Q.front ();
        Q.pop ();
        Viz[nod] = 0;

        for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
            if (Best[it -> first] > Best[nod] + (it -> second) && !Viz[it -> first]){
                Best[it -> first] = Best[nod] + (it -> second);

                Q.push (it -> first);
                Viz[it -> first] = 1;
                InQ[it -> first] ++;

                if (InQ[it -> first] >= N){
                    out << "Ciclu negativ!";
                    return 0;
                }
            }
    }

    for (i = 2; i <= N; i ++)
        out << Best[i] << " ";

    return 0;
}