#include<bits/stdc++.h>

#define MAXN 10004

#define LL long long

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

struct Milk{

    int x,y,t;

    friend bool operator >(const Milk &a,const Milk &b){

        return a.y>b.y;

    }

    friend bool operator <(const Milk &a,const Milk &b){

        return a.y<b.y;

    }

    Milk(){}

    Milk(int a,int b,int c){

        x=a;y=b;t=c;

    }

}milk[MAXN];

vector<LL> solve(const vector<Milk> &a,int dest){

    //调用引用，减小常数

    //背包算出停在dest点花费最小时间

    //若dest为0则不限制停在哪一点

    vector<LL> c(a.size(),INF);

    vector<LL> t(a.size(),INF);

    c[]=(dest==-)?:abs(dest-a[].y);

    t[]=;

    for(int i=;i<a.size();++i){

        int len=abs(a[i].y-a[i-].y);

        for(int j=;j<i;++j)t[j]+=len;

        for(int j=i;j>=;--j)t[j]=min(t[j],t[j-]+a[i].t);

        for(int j=;j<=i;++j){

            LL tmp=t[j]+(dest==-?:abs(dest-a[i].y));

            c[j]=min(c[j],tmp);

        }

    }

    return c;

}

vector<LL> Merge(const vector<LL> &a,const vector<LL> &b){

    vector<LL> c(a.size()+b.size()-,INF);

    for(int i=;i<a.size();++i){

        for(int j=;j<b.size();++j){

            c[i+j]=min(c[i+j],a[i]+b[j]);

        }

    }

    //两个参数分别是朝向两个方向喝多少瓶牛奶花费最少时间，把这俩合并

    return c;

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n,m,k;

        scanf("%d %d %d",&n,&m,&k);

        vector<int> disc;

        disc.push_back();

        for(int i=;i<=k;i++){

            scanf("%d %d %d",&milk[i].x,&milk[i].y,&milk[i].t);

            disc.push_back(milk[i].x);

        }

        sort(disc.begin(),disc.end());

        disc.erase(unique(disc.begin(),disc.end()),disc.end());

        //去重

        vector<Milk> a[MAXN];

        LL Ans[MAXN];

        for(int i=;i<disc.size();++i)a[i].clear();

        for(int i=;i<=k;++i){

            int tmp=lower_bound(disc.begin(),disc.end(),milk[i].x)-disc.begin();

            a[tmp].push_back(milk[i]);

            Ans[i]=INF;

        }

        //将行离散化

        for(int i=;i<disc.size();++i){

            sort(a[i].begin(),a[i].end());

        }

        vector<LL> f[];//存储结果

        vector<Milk> t=a[];//存储当前行 

        t.insert(t.begin(),Milk(,,));

        f[]=solve(t,(m+)/);

        vector<LL> g=solve(t,-);

        for(int i=;i<t.size();++i)Ans[i]=min(Ans[i],g[i]);

        for(int i=;i<disc.size();++i) {

            vector<Milk>::iterator sp=lower_bound(a[i].begin(),a[i].end(),Milk(i,(m+)/,));

            vector<Milk> t0(a[i].begin(),sp);

            vector<Milk> t1(sp,a[i].end());

            t0.push_back(Milk(i,(m+)/,));

            reverse(t0.begin(),t0.end()); 

            t1.insert(t1.begin(),Milk(i,(m+)/,));

            vector<LL> f0,f1,g0,g1;

            f0=solve(t0,(m+)/);

            f1=solve(t1,(m+)/);

            g0=solve(t0,-);

            g1=solve(t1,-);

            //向两个方向分别背包 

            g0=Merge(f1,g0);

            g1=Merge(f0,g1);

            vector<LL> g(g0.size());

            for(int j=;j<g.size();++j){

                g[j]=min(g0[j],g1[j]);

            }

            g=Merge(f[(i-)&],g);

            //把每层的背包合并 

            f[i&]=Merge(f[(i-)&],Merge(f0,f1));

            for(int j=;j<g.size();++j) {

                Ans[j]=min(Ans[j],g[j]+=disc[i]-disc[i-]);

                f[i&][j]+=disc[i]-disc[i-];

            }

        }

        for(int i=;i<k;i++){

            printf("%lld ",Ans[i]);

        }

        printf("%lld\n",Ans[k]);

    }

}