#include <fstream>
#include <vector>
#include <deque>
#define lim 50001
#define INF 1 << 30

using namespace std;

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

struct P{
    int vecin, cost;
}b;

vector <P > v[lim];
deque <int > C;

bool is_in_tail[lim], CicluNeg, vis[lim];
int n, m, x, node, new_node, costMin[lim], cnt[lim];

void bfs(int x){
    C.push_front(x);
    //is_in_tail[x] = 1;
    cnt[x] = 1;
    CicluNeg = false;
    while (!C.empty() && !CicluNeg){
        node = C.front();
        vis[node] = 1;
        C.pop_front();
        for (int i = 0; i < int(v[node].size()); i++){
            new_node = v[node][i].vecin;
            if (v[node][i].cost + costMin[node] < costMin[new_node]){
                costMin[new_node] = v[node][i].cost + costMin[node];
                if (!vis[new_node]){
                    /*if (!is_in_tail[new_node])*/ C.push_back(new_node);
                    //is_in_tail[new_node] = 1;
                    cnt[new_node]++;
                    if (cnt[new_node] > n) CicluNeg = true;
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x;
        fin >> x >> b.vecin >> b.cost;
        v[x].push_back(b);
    }
    for (int i = 2; i <= n; i++){
        costMin[i] = INF;
    }
    bfs(1);
    if (CicluNeg) fout << "Ciclu negativ!";
        else for (int i = 2; i <= n; i++){
            fout << costMin[i] << " ";
        }
    return 0;
}