#include<bits/stdc++.h>
using namespace std;
const int N = 5*10e5+1;
struct node{
	unsigned long long t,x,y;
	bool operator <(const node &a){
		return t> a.t;
	}
}h[N];
unsigned long long n,m;
unsigned long long k;
unsigned long long bj[N];
bool check(unsigned long long time){
	unsigned long long temp=0;
//	if(time==1){
//		int coo=0;
//		for(int i = 1;i<=m;i++){
//			if(h[i].t==1)coo++;
//			if(coo>2){
//				return false;
//			}
//		}
//	}
	for(int i =1;i<=m;i++){
		if(h[i].t>time){
			break;
		}
		else if((time+1-h[i].t-bj[h[i].x]+1)*k<h[i].y){
			continue;
		}
		else{
			if(temp<h[i].t){
			temp=h[i].t;
			}
			unsigned long long cnt=time-h[i].t-(h[i].y/k)-bj[h[i].x];
			if(time==1){
				cnt++;
			}
			bj[h[i].x]+=cnt;
			temp+=cnt; 
//			cout<<temp<<"打表temp->坐标"<<h[i].x<<" "<<time<<endl;
		}
			if(temp>time){
			return false;
		}
	}
	if(temp>time){
		return false;
		}
	return true;
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;		
	cin>>h[1].t>>h[1].x>>h[1].y;
	int st=1;
	for(int i = 2;i<=m;i++){
		cin>>h[i].t>>h[i].x>>h[i].y;
		if(h[i].x!=h[i-1].x){
			st=0;
		}
	}
	if(st==1){
		cout<<"-1"<<endl;
	}
	else{
		sort(h+1,h+m+1);
		 unsigned long long  l=0,r=1e18+1;
		while(l+1<r){
			memset(bj,0,sizeof(bj));
			unsigned long long mid=(l+r)>>1;
			if(check(mid))l=mid;
			else r=mid;
		}
		cout<<l<<endl;
		
	}
	
	return 0;
	
	
}