#include<stdio.h>
#include<vector>
#include<queue>

#define MAXN 50001
#define MARE 2000000000

using namespace std;

FILE *in, *out;

struct mu
{
    int la, co;
};

vector <mu> g[MAXN];
queue <int> qbf;

bool inq[MAXN];
int n, m, viz[MAXN], d[MAXN];

void belfo(int nod)
{
    for(int i = 1; i <= n; i++) {
        d[i] = MARE;
    }
    d[nod] = 0;
    qbf.push(nod);
    inq[nod] = true;
    viz[nod] = 1;

    while(!qbf.empty()) {
        int cur = qbf.front();
        qbf.pop();
        inq[cur] = false;
        for(auto& i : g[cur]) {
            if(d[cur] + i.co < d[i.la]) {
                d[i.la] = d[cur] + i.co;
                if(!inq[i.la]) {
                    qbf.push(i.la);
                    inq[i.la] = true;
                }
                viz[i.la]++;
                if(viz[i.la] > n) {
                    fprintf(out, "Ciclu negativ!");
                    return;
                }
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        if(i != nod) {
            fprintf(out, "%d ", d[i]);
        }
    }
}



int main ()
{

    in = fopen("bellmanford.in", "r");
    out = fopen("bellmanford.out", "w");

    fscanf(in, "%d%d", &n, &m);
    //printf("OK");
    //fflush(stdout);

    for(int i = 0; i < m; i++) {
        int a, b, c;
        fscanf(in, "%d%d%d", &a, &b, &c);
        mu nou;
        nou.la = b;
        nou.co = c;
        g[a].push_back(nou);
    }

    belfo(1);

    fclose(in);
    fclose(out);

    return 0;
}