#include<cstdio>
#include<climits>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long

struct edge
{
    int to, cap, cost, rev;
    edge(int to_, int cap_, int cost_, int rev_):
        to(to_), cap(cap_), cost(cost_), rev(rev_){}
};
const int MAX_V = 402, MAX_N = 200;
vector<edge> G[MAX_V];
int V, preve[MAX_V], prevv[MAX_V], h[MAX_V], dist[MAX_V], a[MAX_N], b[MAX_N], w[MAX_N], N, K;
typedef pair<int, int> P;

inline void add_edge(int from, int to, int cap, int cost)
{
    G[from].push_back(edge(to, cap, cost, G[to].size()));
    G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
}

int min_cost_flow(int s, int t, int f)
{
    memset(h, 0, sizeof(h));
    int res = 0;
    while (f > 0)
    {
        priority_queue<P, vector<P>, greater<P> > que;
        que.push(P(0, s));
        fill(dist, dist + V, INT_MAX);
        dist[s] = 0;
        for (int v, dis; !que.empty(); )
        {
            dis = que.top().first, v = que.top().second;
            que.pop();
            if (dis > dist[v])
                continue;
            for (int i = 0; i < G[v].size(); ++i)
            {
                edge& e = G[v][i];
                if (e.cap && dist[e.to] > dis + e.cost + h[v] - h[e.to])
                {
                    dist[e.to] = dis + e.cost + h[v] - h[e.to],
                    prevv[e.to] = v,
                    preve[e.to] = i;
                    que.push(P(dist[e.to], e.to));
                }
            }
        }
        if (dist[t] == INT_MAX)
            return -1;
        for (int v = 0; v < V; ++v)
            h[v] += dist[v];
        int d = f;
        for (int v = t; v != s; v = prevv[v])
            d = min(d, G[prevv[v]][preve[v]].cap);
        f -= d,
        res += h[t] * d;
        for (int v = t; v != s; v = prevv[v])
        {
            edge& e = G[prevv[v]][preve[v]];
            e.cap -= d,
            G[v][e.rev].cap += d;
        }
    }
    return res;
}


void solve()
{
    for (int i = 0; i < MAX_V; ++i)
        G[i].clear();
    vector<int> x;
    for (int i = 0; i < N; ++i)
    {
        x.push_back(a[i]);
        x.push_back(b[i]);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    int m = x.size();
    int s = m, t = s + 1;
    V = t + 1;
    int res = 0;
    add_edge(s, 0, K, 0);
    add_edge(m - 1, t, K, 0);
    for (int i = 0; i + 1 < m; ++i)
        add_edge(i, i + 1, INT_MAX, 0);
    for (int i = 0; i < N; ++i)
    {
        int u = find(x.begin(), x.end(), a[i]) - x.begin();
        int v = find(x.begin(), x.end(), b[i]) - x.begin();
        add_edge(v, u, 1, w[i]);
        add_edge(s, v, 1, 0);
        add_edge(u, t, 1, 0);
        res -= w[i];
    }
    res += min_cost_flow(s, t, K + N);
    printf("%d\n", -res);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &N, &K);
        for (int i = 0; i < N; ++i)
            scanf("%d%d%d", &a[i], &b[i], &w[i]);
        solve();
    }
    return 0;
}