function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});    
    var lVl = parseInt(input[0][0], 10);
    var lEl = parseInt(input[0][1], 10);
    var graph = [];
    for (var x of input){
        if (x.length ===  2) continue;
        x = x.map(e => parseInt(e, 10));
        if (graph[x[0]] == null) graph[x[0]] = [];
        graph[x[0]][x[1]] = x[2];
    }
    var INF = Number.MAX_SAFE_INTEGER / 2;
    var dp = [];
    for (var j = 0; j < lVl; j++){
        x = graph[j];
        dp.push([]);
        if (x == null) {
            dp[dp.length - 1] = Array(lVl).fill(INF, 0, lVl);
            dp[dp.length - 1][dp.length - 1] = 0;
            continue;
        }
        for (var i = 0; i < lVl; i++){
            if (i === dp.length - 1) dp[dp.length - 1].push(0);
            else if (x[i] == null) dp[dp.length - 1].push(INF);
            else dp[dp.length - 1].push(x[i]);
        }
    }
    for(var k = 0; k < lVl; k++){
        for(var i = 0; i < lVl; i++){
            for(var j = 0; j < lVl; j++) {
                if (dp[i][j] === INF && (dp[i][k] === INF || dp[k][j] === INF)) dp[i][j] = INF;
                else dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    var str;
    var flag = true;
    var v_ans = [];
    whole_loop:
    for (var j = 0; j < dp.length; j++){
        x = dp[j];
        for (var i = 0; i < x.length; i++){
            if (i === j && x[i] < 0){
                console.log("NEGATIVE CYCLE");
                flag = false;
                break whole_loop;
            } else if  (x[i] === INF){
                x[i] = "INF";
            }
        }
        str = x.join(" ");
        v_ans.push(str);
    }
    if (flag) {
        console.log(v_ans.join("\n"));
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));
