module.exports=function(t){var r={};function e(n){if(r[n])return r[n].exports;var i=r[n]={i:n,l:!1,exports:{}};return t[n].call(i.exports,i,i.exports,e),i.l=!0,i.exports}return e.m=t,e.c=r,e.d=function(t,r,n){e.o(t,r)||Object.defineProperty(t,r,{enumerable:!0,get:n})},e.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},e.t=function(t,r){if(1&r&&(t=e(t)),8&r)return t;if(4&r&&"object"==typeof t&&t&&t.__esModule)return t;var n=Object.create(null);if(e.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:t}),2&r&&"string"!=typeof t)for(var i in t)e.d(n,i,function(r){return t[r]}.bind(null,i));return n},e.n=function(t){var r=t&&t.__esModule?function(){return t.default}:function(){return t};return e.d(r,"a",r),r},e.o=function(t,r){return Object.prototype.hasOwnProperty.call(t,r)},e.p="",e(e.s=0)}([function(t,r,e){"use strict";var n=e(1);e(2)(n.readFileSync("/dev/stdin","utf8"))},function(t,r){t.exports=require("fs")},function(t,r,e){"use strict";var n=e(3),i=e(5);t.exports=function(t){var r=new n(t);i(r)}},function(t,r,e){"use strict";var n=e(4);t.exports=class{constructor(t){var r=t.trim().split(/\s+/g);this.inp=new n(r)}inr(){return this.inp.deq()}in(){return parseInt(this.inp.deq(),10)}fin(){this.inp.clear()}}},function(t,r,e){"use strict";t.exports=class{constructor(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:[];this.size=t.length,this.items=t,this.ind=0}enq(t){this.size+=1,this.items.push(t)}deq(){var t=this.items[this.ind];return this.size-=1,this.ind+=1,t}clear(){this.items=[],this.size=0,this.ind=0}}},function(t,r,e){"use strict";var n=e(6);t.exports=function(t){for(var r=t.in(),e=t.in(),i=new Array(r),o=99999999999999,s=0;s<r;s++)i[s]=new Array(r).fill(o);for(var u=0;u<e;u++){var c=t.in(),f=t.in(),a=t.in();i[c][f]=a}for(var l=n(i,o),p=[],v=0;v<r;v++){var d=[];if(l[v][v]<0)return void console.log("NEGATIVE CYCLE");for(var h=0;h<r;h++)l[v][h]==o?d.push("INF"):d.push(l[v][h].toString());p.push(d.join(" "))}console.log(p.join("\n"))}},function(t,r,e){"use strict";t.exports=function(t){for(var r=arguments.length>1&&void 0!==arguments[1]?arguments[1]:99999999999999,e=t.length,n=new Array(e),i=0;i<e;i++)n[i]=t[i].concat(),n[i][i]=0;for(var o=0;o<e;o++)for(var s=0;s<e;s++)for(var u=0;u<e;u++)if(n[s][o]!=r&&n[o][u]!=r){var c=n[s][o]+n[o][u];n[s][u]>c&&(n[s][u]=c)}return n}}]);
