#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

#define F first
#define S second

const int MAXN = 1e4 + 10;

int n, m, k, sec[MAXN], sz, r[MAXN], c[MAXN], t[MAXN];
vector<pii> vec[MAXN];
ll ans[MAXN], d[2][MAXN], _d[2][MAXN];
ll d1[MAXN], d2[MAXN];
int srt[MAXN];

void smin(ll &x, ll y){x = min(x, y);}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		cin >> n >> m >> k;
		sz = 0;
		for (int i = 0; i < k; i++) cin >> r[i] >> c[i] >> t[i], r[i]--, c[i]--, sec[sz++] = r[i];
		sort(sec, sec + sz);
		sz = unique(sec, sec + sz) - sec;
		for (int i = 0; i < sz; i++) vec[i].clear();
		for (int i = 0; i < k; i++){
			r[i] = lower_bound(sec, sec + sz, r[i]) - sec;
			vec[r[i]].push_back({c[i], t[i]});
		}
		for (int i = 0; i < sz; i++) sort(vec[i].begin(), vec[i].end());
	
		memset(ans, 63, sizeof(ans));
		ans[0] = 0;
		memset(d, 63, sizeof(d));
		d[0][0] = sec[0];
		d[1][0] = sec[0] + (m-1);
		int curSm = 0;
		for (int i = 0; i < sz; i++){
			memset(_d, 63, sizeof(_d));
			//0

			int cnt = 0;
			memset(d1, 63, sizeof(d1));
			memset(d2, 63, sizeof(d2));
			d1[0] = 0;
			d2[0] = 0;
			int dif = sec[i+1] - sec[i];
			for (auto x:vec[i]){
				srt[cnt++] = x.S;
				for (int i = cnt-1; i && srt[i] < srt[i-1]; i--)
					swap(srt[i], srt[i-1]);

				ll sm = 0;
				for (int i = 0; i < cnt; i++){
					sm += srt[i];
					smin(d1[i+1], sm + x.F);
					smin(d2[i+1], sm + x.F*2);
				}
			}
			for (int t1 = 0; t1 <= curSm; t1++) {
				ll sm = 0;
				for (int t2 = 0; t2 <= (int)vec[i].size(); t2++) {
					smin(ans[t1+t2], d[0][t1] + d1[t2]);
					smin(_d[0][t1+t2], d[0][t1] + d2[t2] + dif);
					smin(_d[1][t1+t2], d[0][t1] + (m-1) + sm + dif);
					sm += srt[t2];
				}
			}

			cnt = 0;
			memset(d1, 63, sizeof(d1));
			memset(d2, 63, sizeof(d2));
			d1[0] = d2[0] = 0;
			reverse(vec[i].begin(), vec[i].end());
			for (auto x:vec[i]){
				srt[cnt++] = x.S;
				for (int i = cnt-1; i && srt[i] < srt[i-1]; i--)
					swap(srt[i], srt[i-1]);

				ll sm = 0;
				for (int i = 0; i < cnt; i++){
					sm += srt[i];
					smin(d1[i+1], sm + (m-1-x.F));
					smin(d2[i+1], sm + (m-1-x.F)*2);
				}
			}
			for (int t1 = 0; t1 <= curSm; t1++) {
				ll sm = 0;
				for (int t2 = 0; t2 <= (int)vec[i].size(); t2++){
					smin(ans[t1+t2], d[1][t1] + d1[t2]);
					smin(_d[1][t1+t2], d[1][t1] + d2[t2] + dif);
					smin(_d[0][t1+t2], d[1][t1] + (m-1) + sm + dif);
					sm += srt[t2];
				}
			}

			memcpy(d, _d, sizeof(d));
			curSm += (int)vec[i].size();
		}

		for (int i = 1; i <= k; i++)
			cout << ans[i] << " ";
		cout << "\n";
	}
	return 0;
}