#include <bits/stdc++.h>
using namespace std;


#define inf64 INT64_MAX/2
#define inf32 INT32_MAX/2
#define ll long long
#define int ll
#define pii pair<int,int>
#define endl '\n'
#define vv vector
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define its(a)  a.begin()+1,a.end()
#define minV *min_element
#define maxV *max_element
#define sumV(a) accumulate(its(a),0ll)
int _;
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
ll mpow(ll x, ll y, ll mod);






void solve() {


	int n, m; cin >> n >> m;
	int r; cin >> r;
	n++, m++;
	
	queue<pair<int, pii>>q;

	vv<vv<bool>>flag(n + 1, vv<bool>(m + 1));

	q.push({ 0,{ 1,1 } });
	map<int, set<pii>>all;
	for (int i = 1; i <= r; i++) {
		int t, d, cod;
		cin >> t >> d >> cod;
		cod++;
		all[t].insert({ d,cod });
	}


	while (q.size()) {
		auto nd = q.front();
		q.pop();
		int t = nd.first;
		int x = nd.second.first;
		int y = nd.second.second;
 		flag[x][y] = 0;
		if (all[t].count({ 1,x }))
			continue;
		if (all[t].count({ 2,y }))
			continue;

		if (x == n && y == m){
			cout << t << endl;
			return;
		}
		if (x + 1 <= n && !flag[x + 1][y])
			q.push({ t + 1,{x + 1,y} }), flag[x + 1][y] = 1;
		if (y + 1 <= m && !flag[x][y + 1])
			q.push({ t + 1,{x,y + 1} }), flag[x][y + 1] = 1;
		if (!flag[x][y])
			q.push({ t + 1,{x,y} }), flag[x][y] = 1;
	}
	cout << -1 << endl;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	_ = 1;
	cin >> _;

	while (_--) {
		solve();
	}

	return 0;
}

ll mpow(ll x, ll y, ll mod) {
	x %= mod;
	ll s = 1;
	while (y) {
		if (y & 1) {
			s *= x;
			s %= mod;
		}
		x *= x;
		x %= mod;
		y >>= 1;
	}
	return s;
}