#include <fstream>
#include <queue>

const int MAX_N = 50001, MAX_M = 250001, INF = 300000000;

int n, m;
int list[MAX_N], next[MAX_M], at[MAX_M], cost[MAX_M], count;
std::queue<int> q;
int nrq[MAX_N], d[MAX_N];
bool inq[MAX_N];

inline void add(int from, int to, int cst) {
    ++count;
    at[count] = to;
    cost[count] = cst;
    next[count] = list[from];
    list[from] = count;
}

int main() {
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");
    int i, p, x, y, c;
    in >> n >> m;
    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        add(x, y, c);
    }
    for (i = 2; i <= n; ++i) d[i] = INF;
    d[1] = 0;
    q.push(1);
    inq[1] = true;
    nrq[1] = n - 1;
    while (!q.empty()) {
        x = q.front();
        q.pop();
        inq[x] = false;
        for (p = list[x]; p != 0; p = next[p]) {
            y = at[p];
            c = cost[p];
            if (d[x] + c < d[y]) {
                d[y] = d[x] + c;
                if (!inq[y]) {
                    q.push(y);
                    inq[y] = true;
                }
                if (++nrq[y] == n) {
                    out << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for (i = 2; i <= n; ++i) out << d[i] << ' ';
    return 0;
}