# include <fstream>
# include <queue>
# include <vector>
# define MAXN 50010
# define MAXM 250010
# define pb   push_back
# define INF  0x3f3f3f3f

using namespace std;

queue<int> q;
vector<int> L[MAXN], C[MAXN];
int n, m;
int cost[MAXN];
int viz[MAXN];
bool negative;

bool bellmanford() {
    int curent, vecin, pret;
    q.push(1);
    while (!q.empty()) {
        curent = q.front();
        for (unsigned int i=0; i<L[curent].size(); ++i) {
            vecin = L[curent][i];
            pret = C[curent][i];
            if (cost[vecin] > cost[curent] + pret) {
                cost[vecin] = cost[curent] + pret;
                viz[vecin] = 1 + viz[curent];
                q.push(vecin);
                if (viz[vecin] == n+1)
                    return 1;
            }
        }
        q.pop();
    }
    return 0;
}

int main() {
    ifstream fin("bellmanford.in");
    fin >> n >> m;
    int x, y, c;
    for (int i=1; i<=n; ++i) {
        fin >> x >> y >> c;
        L[x].pb(y);
        C[x].pb(c);
    }
    fin.close();

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


    ofstream fout("bellmanford.out");
    if (bellmanford())
        fout << "Ciclu negativ!";
    else for (int i=2; i<=n; ++i)
        fout << cost[i] << " ";
    fout.close();
    return 0;
}