#include<fstream>
#include<vector>
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
int coada[50001],hz[50001],n,m;
int in_coada[50005],val[50005];
vector< pair<int,int> > v[50005];
int bellman (int nod) {
    int st = 0, dr = 0;
    hz[nod] = 1;
    coada[++st] = nod;
    in_coada[nod] = 1;
    for ( st = 1, dr = 1; st <= dr; st ++) {
        int a = coada[st];
        in_coada[a] = 0;
        for (int i = 0; i < v[a].size(); i ++) {
            int b = v[a][i].first;
            int cost = v[a][i].second;
            if (in_coada[b] == 0 ) {
                if (val[b] > val[a] + cost) {
                    coada[++dr] = b;
                    in_coada[b] = 1;
                    hz[b] ++;
                    val[b] = val[a] + cost;
                    if (hz[b] == n+1) {
                        return -1;
                    }
                }
            }
            else {
                if (val[b] > val[a] + cost) {
                    val[b] = val[a] + cost;
                }
            }
        }
    }
    return 0;
}
int main (void) {
    in >> n >> m;
    int a,b,c;
    for (int i = 1; i <= m; i ++) {
        in >> a >> b >> c;
        v[a].push_back ( make_pair(b,c));
    }
    for (int i = 2; i <= n; i ++) {
        val[i] = 1e9;
    }
    int aux = bellman (1);
    if (aux == -1) {
        out << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= n; i ++) {
            out << val[i] <<" ";
        }
    }

    return 0;
}