#include <stdio.h>
const long long int INF=100000000000000000;
int main(){
	int n,m,l,r,c;
	long long int g[110][110];
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		if(i==j)g[i][j]=0;
		else g[i][j]=INF; 
	}
	while(m--){
		scanf("%d%d%d",&l,&r,&c);
		g[l][r]=c;
	}
	for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		if(g[i][k]==INF||g[k][j]==INF)continue;
	if(g[i][k]+g[k][j]<g[i][j])g[i][j]=g[i][k]+g[k][j];
	}
	for(int i=0;i<n;i++)if(g[i][i]<0){
	printf("NEGATIVE CYCLE\n");
	return 0;
	}
	for(int i=0;i<n;i++){
		if(g[i][0]==INF)printf("INF");
		else printf("%lld",g[i][0]);
		for(int j=1;j<n;j++){
			if(g[i][j]==INF)printf(" INF");
			else printf(" %lld",g[i][j]);
		}
		printf("\n");
	}
}
#include "bits/stdc++.h"
#define ll long long
#define lld long double
#define MOD 1000000007
#define inf 1000000007
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
 
using namespace std;


#define endl '\n'
// #define int ll

signed main() {
	fast;

	int h,w;
	cin>>h>>w;

	pii v[200002];
	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;

	map<int,int> mp;
	for(int i=1;i<=w;i++) mp[i] = 0;

	map<int,int> mini = {{0,w}};

	for(int i=0;i<h;i++) {
		int r = v[i].s;

		auto it = mp.lower_bound(v[i].f);


		if(r==w) {
			while(it!=mp.end() && it->f <= r) {
				auto it1 = it++;
				auto it2 = mini.find(it1->s);
				if(it2->s==1) mini.erase(it2);
				else it2->s --;
				mp.erase(it1);
			}

			if(mini.size()==0) cout<<-1<<endl;
			else cout<<mini.begin()->f+i+1<<endl;
		}
		else {
			int mn = inf;

			while(it!=mp.end() && it->f <= r) {
				mn = min(mn, r+1-(it->f)+(it->s));
				auto it1 = it++;
				auto it2 = mini.find(it1->s);
				if(it2->s==1) mini.erase(it2);
				else it2->s --;
				mp.erase(it1);
			}

			if(mn<inf) {
				if(it!=mp.end() && it->f == r + 1) {
					if(it->s > mn) {
						auto it1 = mini.find(it->s);
						if(it1->s ==1) mini.erase(it1);
						else it1->s --;
						mini[mn]++;
						it->s = mn;
					}
				}
				else {
					mp.emplace_hint(it,r+1,mn);
					mini[mn]++;
				}
				cout<<mini.begin()->f+i+1<<endl;
			}
			else {
				if(mini.size()==0) cout<<-1<<endl;
				else cout<<mini.begin()->f+i+1<<endl;
			}

		}

	}
}