#include <iostream>

using namespace std;
using LL = long long;

const LL INF = 1L << 32;

LL G[101][101];

int main() {

    int V, E;
    cin >> V >> E;

    //
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (i == j) G[i][j] = 0;
            else G[i][j] = INF;
        }
    }

    for (int i = 0; i < E; i++) {
        int s, t, d;
        cin >> s >> t >> d;
        G[s][t] = d;
    }

    //
    bool negative_cycle = false;

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            if (G[i][k] == INF) continue;
            for (int j = 0; j < V; j++) {
                if (G[k][j] == INF) continue;
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                if (i == j && G[i][j] < 0) {
                    negative_cycle = true;
                    goto outer;
                }
            }
        }
    }
    outer:

    //
    if (negative_cycle) {
        cout << "NEGATIVE CYCLE" << endl;
    } else {
        for (int i = 0; i < V; i++) {
            int k = 0;
            for (int j = 0; j < V; j++) {
                if (k++) cout << " ";
                cout << (G[i][j] != INF ? to_string(G[i][j]) : "INF");
            }
            cout << endl;
        }
    }
}

#include <iostream>
#include <algorithm>
using namespace std;

bool isSmallAlphabet(char& ch) {
  /* a ~ z(ascii) : 97 ~ 122 */
  if('a' <= ch && ch <= 'z') return true;
  else return false;
}

bool isHit(string& str) {
  if(str.find("the") != str.npos) return true;
  else if(str.find("this") != str.npos) return true;
  else if(str.find("that") != str.npos) return true;
  else return false;
}

char shiftIndex(char ch) {
  if(isSmallAlphabet(ch)) {
    ch += 1;
    /* ???????????????????°?????????§???????????£??????*/
    if(!isSmallAlphabet(ch)) {
      ch -= 26;
    }
  }
  return ch;
}

/* ????????¶??????????§£??? */
void CaesarCipher(string str) {
  
  /* p??????????????¢??????????????????????????????????????? */
  for(int p = 0; p < 26; ++p) {

    transform(str.begin(), str.end(), str.begin(), shiftIndex);

    /* Find "the" or "this" or "that" */
    if(isHit(str)) {
      cout << str << endl;
    }
  }
}

int main() {
  string str;
  while(getline(cin, str)) {
    CaesarCipher(str);
  }
  return 0;
}