import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

struct Queue(T) {
    private {
        size_t cap, head, tail;
        T[] data;
    }

    this (size_t n) in {
        assert(n > 0, "The capacity of a queue must be a positive integer.");
    } body {
        cap = n + 1;
        data = new T[](cap);
    }

    void clear() {
        head = tail = 0;
    }

    bool empty() {
        return head == tail;
    }

    bool full() {
        return head == (tail + 1) % cap;
    }

    size_t length() {
        return head <= tail ? tail - head : cap - head + tail;
    }

    T front() in {
        assert(!empty, "The queue is empty.");
    } body {
        return data[head];
    }

    void removeFront() in {
        assert(!empty, "The queue is empty.");
    } body {
        (++head) %= cap;
    }

    alias popFront = removeFront;

    void insertBack(T x) in {
        assert(!full, "The queue is full.");
    } body {
        data[tail++] = x;
        tail %= cap;
    }

    alias insert = insertBack;

    T[] array() {
        return head <= tail ? data[head .. tail].dup : data[head .. $] ~ data[0 .. tail];
    }

    string toString() {
        import std.format : format;

        if (head <= tail) {
            return format("[%(%s, %)]", data[head .. tail]);
        }
        else {
            return format("[%(%s, %)", data[head .. $]) ~ format(", %(%s, %)]", data[0 .. tail]);
        }
    }
}




unittest {
    auto a = Queue!(int)(5);

    //a.front;
    a.insert(2);
    a.insert(5);
    a.insert(3);

    //a.insert(8);

    import std.stdio;

    a.removeFront;
    a.removeFront;

    a.insert(11);
    a.insert(7);

    a.insert(123);
    a.insert(543);

    a.removeFront;
    a.removeFront;
    a.removeFront;

    a.insert(1212);
    a.insert(9898);
    a.insert(3154);

    a.removeFront;
    a.removeFront;
    a.removeFront;
    a.removeFront;
    a.removeFront;
}

unittest {
    auto q = Queue!(int)(5);
    assert(q.empty);

    q.insert(3);
    q.insert(1);
    q.insert(5);
    q.insert(4);
    q.insert(8);

    // q = [3,1,5,4,8]

    auto hoge = q.array;

    assert(hoge == [3,1,5,4,8]);

    assert(q.full);

    q.popFront();
    q.popFront(); 

    // q = [5,4,8]

    hoge = q.array;

    assert(hoge == [5,4,8]);
    hoge[0] = 3;
    hoge[2] = 11;

    assert(q.front == 5);
    assert(q.length == 3);

    q.popFront();
    q.popFront();

    // q = [8]

    q.insert(11);
    q.insert(-8);

    // q = [8,11,-8]

    assert(q.front == 8);
    assert(q.length == 3);

    q.insert(23);
    q.insert(31);

    // q = [8,11,-8,23,31]

    assert(q.full);
    assert(q.length == 5);

    auto a = new int[](0);

    foreach (e ; q) {
        a ~= e;
    }

    assert(a == [8, 11, -8, 23, 31]);

    foreach (i ; 0 .. 5) {
        q.popFront();
    }

    assert(q.length == 0);
    assert(q.empty);

    hoge = q.array;
    assert(hoge == []);
}

unittest {
    auto q = Queue!(string)(4);

    q.insert("Hello");
    q.insert(",");
    q.insert("World");
    q.insert("!");

    auto hoge = q.array;
    assert(hoge == ["Hello", ",", "World", "!"]);

    assert(q.full);
    assert(q.length == 4);

    q.popFront();
    q.popFront();

    assert(q.front == "World");
    assert(q.length == 2);

    q.clear();

    assert(q.empty);
    assert(q.length == 0);

    q.insert("hoge");
    q.insert("fuga");
    q.insert("melon");

    q.popFront();
    q.popFront;
    q.popFront;

    q.insert("hayo");
    q.insert("hoge");
    q.insert("pippi");

    hoge = q.array;
    hoge[0] = "aho";
    assert(q.front == "hayo");

    q.insert("huni");

    q.popFront;
    q.popFront;

    q.insert("ueue");

    assert(q.front == "pippi");
    assert(q.length == 3);
}



enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


void main() {
    int N, M;
    scan(N, M);

    auto dist = new long[][](N, N);
    fillAll(dist, infl);
    foreach (i ; 0 .. N) {
        dist[i][i] = 0;
    }

    foreach (i ; 0 .. M) {
        int ui, vi, ci;
        scan(ui, vi, ci);
        dist[ui][vi] = ci;
    }

    foreach (k ; 0 .. N) {
        foreach (i ; 0 .. N) {
            foreach (j ; 0 .. N) {
                if (dist[i][k] == infl || dist[k][j] == infl) continue;
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    bool nc = false;

    foreach (i ; 0 .. N) {
        if (dist[i][i] < 0) nc = true;
    }

    if (nc) {
        writeln("NEGATIVE CYCLE");
        return;
    }

    foreach (i ; 0 .. N) {
        foreach (j ; 0 .. N) {
            write(dist[i][j] < infl ? dist[i][j].to!string : "INF");
            write(j == N - 1 ? '\n' : ' ');
        }
    }
}



Measured memory_bytes: 2672