#include <bits/stdc++.h>

using namespace std;

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


int n,m,a,b,cost,d[50005],mark[50005];
vector <pair<int,int>> v[50005];
queue <int> Q;

void Bellmanford(){
    while(!Q.empty()){
        int j = Q.front();
        Q.pop();
        for (int k = 0; k < v[j].size(); k++){
            if (d[j] + v[j][k].second < d[v[j][k].first]){
                d[v[j][k].first] = d[j] + v[j][k].second;
                Q.push(v[j][k].first);
                mark[v[j][k].first]++;
                if (mark[v[j][k].first] == n){
                    fout << "Ciclu negativ!";
                    exit(0);
                }
            }
        }
    }
}


int main()
{
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>a>>b>>cost;
    v[a].push_back({b, cost});
}
for (int i = 1; i <= n; i++){
    d[i] = 999999999;
}
Q.push(1);
mark[1]++;
d[1] = 0;
Bellmanford();
int ok = 0;
for (int j = 1; j <= n && ok == 0; j++){
    for (int k = 0; k < v[j].size(); k++){
        if (d[j] + v[j][k].second < d[v[j][k].first]){
            ok = 1;
            break;
        }
    }
}
for (int i = 2; i <= n; i++){
    fout << d[i] << " ";
}

return 0;
}