// bellman-ford cu BFS / queue
#include <fstream>
#include <climits>
#include <queue>

typedef long long ll;
std::ifstream fin ("bellmanford.in");
std::ofstream fout ("bellmanford.out");

int const INF = INT_MAX;
int const nmax = 50005;
int const mmax = 250005;

struct muchie {
    int nod;
    int cost;
};
std::vector <muchie> adjacency[nmax];

int length[nmax];
bool isInQueue[nmax];
int nrAparitii[nmax];
std::queue <int> q;
bool ciclu;

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int nod1, nod2, cost;
        fin >> nod1 >> nod2 >> cost;
        adjacency[nod1].push_back({nod2, cost});
    }
    for (int i = 2; i <= n; i++)
        length[i] = INF;
    q.push(1);
    isInQueue[1] = true;
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        int cnt = adjacency[front].size();
        isInQueue[front] = false;
        for (int i = 0; i < cnt; i++) {
            if (length[front] + adjacency[front][i].cost < length[adjacency[front][i].nod]) {
                length[adjacency[front][i].nod] = length[front] + adjacency[front][i].cost;
                if (!isInQueue[adjacency[front][i].nod]) {
                    q.push(adjacency[front][i].nod);
                    nrAparitii[adjacency[front][i].nod]++;
                    isInQueue[adjacency[front][i].nod] = true;
                    if (nrAparitii[adjacency[front][i].nod] > n) {
                        ciclu = true;
                        while (!q.empty())
                            q.pop();
                        break;
                    }
                }
            }
        }
    }
    if (ciclu == true)
        fout << "Ciclu negativ!";
    else {
        for (int i = 2; i <= n; i++)
            fout << length[i] << " ";
    }
    return 0;
}