# 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;
int viz[MAXN];
long long d[MAXN];

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

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

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


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