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

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

const int INF = 0x3f3f3f3f;

#define VI vector<int>
#define VVI vector<VI>

int n, m;
VVI drum;

void RoyFloyd() {
    for (int k = 1; k <= n; ++k) {
        for (int x = 1; x <= n; ++x) {
            for (int y = 1; y <= n; ++y) {
                if (x == y) {
                    drum[x][y] = 0;
                } else {
                    if (drum[x][y] > drum[x][k] + drum[k][y] && drum[x][k] != INF && drum[k][y] != INF) {
                        drum[x][y] =  drum[x][k] + drum[k][y];
                    }
                }
            }
        }
    }
}

void printDrum() {
    for (int i = 1; i <= 1; ++i) {
        for (int j = 2; j <= n; ++j) {
           if (drum[i][j] == INF) {
               fout << "| ";
           } else {
                fout << drum[i][j] << ' ';
            }
        }
        fout << '\n';
    }
}

int main() {
    fin >> n >> m;
    drum = VVI(n + 1, VI(n + 1, INF));
    for (int i = 0; i < m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        drum[x][y] = c;
    }
    RoyFloyd();
    for (int k = 1; k <= n; ++k) {
        for (int x = 1; x <= n; ++x) {
            for (int y = 1; y <= n; ++y) {
                if (x == y) {
                    drum[x][y] = 0;
                } else {
                    if (drum[x][y] > drum[x][k] + drum[k][y] && drum[x][k] != INF && drum[k][y] != INF) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    printDrum();
}