#include <fstream>
#include <queue>
#include <list>
#define INF 1<<30
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

queue<int> Q;
list<pair<int, int> > graf[50010];
list<pair<int, int> >::iterator it;
int n, m, x, y, c, i, j, iterations, dist[50010];

int main() {
    fin>>n>>m;
    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
    }
    for (i = 2 ; i <= n ; i++) {
        dist[i] = INF;
    }

    Q.push(1); Q.push(-1);
    while(!Q.empty() && iterations < n) {
        x = Q.front();
        Q.pop();
        if (x != -1) {
            for (it = graf[x].begin() ; it != graf[x].end() ; it++) {
                /// Without checking for already visited?
                if (dist[x] + it -> second < dist[it -> first]) {
                    dist[it -> first] = dist[x] + it -> second;
                    Q.push(it -> first);
                }
            }
        } else {
            iterations++;
            if (!Q.empty() && Q.front() != -1)
                Q.push(-1);
        }
    }

    if (iterations < n) {
        for (i = 2 ; i <= n ; i++) {
            fout<<dist[i]<<' ';
        }
    } else {
        fout<<"Ciclu negativ!";
    }
}