#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int INF = 0x3f3f3f3f;
struct arcul
{
    int y, c;
};

#define VI vector<int>
#define VB vector<bool>
#define VA vector<arcul>
#define VVA vector<VA>
#define Q queue<int>
#define pb push_back

int n, m;
VVA adList;
VI costMin;
bool cicluNegativ = false;

void BellmanFord(int start) {
    Q noduri;
    VB folosit(n + 1, false);
    VI visite(n + 1, 0);
    noduri.push(start);
    costMin[start] = 0;
    while(!noduri.empty() && !cicluNegativ) {
        int nodC = noduri.front();
        noduri.pop();
        ++visite[nodC];
        folosit[nodC] = false;
        if (visite[nodC] > n) {
            cicluNegativ = true;
            return;
        }
        for (auto vecin : adList[nodC]) {
            int costVecin = costMin[nodC] + vecin.c;
            if (costMin[vecin.y] > costVecin) {
                costMin[vecin.y] = costVecin;
                if (!folosit[vecin.y]) {
                    noduri.push(vecin.y);
                    folosit[vecin.y] = true;
                }
            }
        }
    }
}

int main() {
    fin >> n >> m;
    adList = VVA(n + 1);
    costMin = VI(n + 1, INF);
    for (int i = 0; i < m; ++i) {
        arcul u;
        int nod;
        fin >> nod >> u.y >> u.c;
        adList[nod].pb(u);
    }

    BellmanFord(1);
    
    if (cicluNegativ) {
        fout << "Ciclu negativ!";
        return 0;
    }

    for (int nod = 2; nod <= n; ++nod) {
        fout << costMin[nod] << ' ';
    }
}