Here is the code:

#include <iostream>

#include <cmath>

using namespace std;

struct dxy {

int d;

int x;

int y;

};

dxy egcd(int a, int b) {

dxy t1, t2;

if (b == 0) {

t1.d = a;

t1.x = 1;

t1.y = 0;

return t1;

} else {

t1 = egcd(b,a%b);

t2.d = t1.d;

t2.x = t1.y;

t2.y = t1.x - a/b*t1.y;

return t2;

}

}

int solveLinEq(int a, int b, int n) {

dxy t = egcd(a,n);

// cerr << "(" << t.d << "," << t.x << "," << t.y << ")" << endl;

if (b % t.d == 0) {

int period = n/t.d;

int x0 = t.x*(b/t.d) % n;

if (x0 < 0) {

return x0 + (int)(ceil(-x0/(double)period))*period;

//return x0 + ((-x0-1)/period+1)*period;

} else {

return x0 - (int)(floor(x0/(double)period))*period;

//return x0 - (x0/period)*period;

}

} else {

return -1;

}

}

void scenario() {

int n;

cin >> n;

int walk[n];

int cave[n];

int life[n];

for (int i = 0; i < n; ++i) {

cin >> cave

*>> walk*

*>> life**;*

--cave--cave

*;*

}

int days, m;

bool crash = true;

for (m = 1; m <= 1000000 && crash; ++m) {

crash = false;

for (int from = 0; from < n && !crash; ++from) {

for (int to = from+1; to < n && !crash; ++to) {

if (walk[from] > walk[to]) {

days = solveLinEq(walk[from]-walk[to],cave[to]-cave[from],m);

} else {

days = solveLinEq(walk[to]-walk[from],cave[from]-cave[to],m);

}

if (days >= 0 && days <= life[from] && days <= life[to]) {

crash = true;

}

}

}

}

cout << m-1 << endl;

}

int main() {

int n;

cin >> n;

for (int i = 0; i < n; ++i)

scenario();

return 0;

}}

int days, m;

bool crash = true;

for (m = 1; m <= 1000000 && crash; ++m) {

crash = false;

for (int from = 0; from < n && !crash; ++from) {

for (int to = from+1; to < n && !crash; ++to) {

if (walk[from] > walk[to]) {

days = solveLinEq(walk[from]-walk[to],cave[to]-cave[from],m);

} else {

days = solveLinEq(walk[to]-walk[from],cave[from]-cave[to],m);

}

if (days >= 0 && days <= life[from] && days <= life[to]) {

crash = true;

}

}

}

}

cout << m-1 << endl;

}

int main() {

int n;

cin >> n;

for (int i = 0; i < n; ++i)

scenario();

return 0;

}