#include <bits/stdc++.h>

using i64 = long long;
using Int = __int128;

struct Point {
    Int x = 0;
    Int y = 0;
    Int z = 0;
};

Point operator+(const Point &a, const Point &b) {
    return {a.x + b.x, a.y + b.y, a.z + b.z};
}

Point operator-(const Point &a, const Point &b) {
    return {a.x - b.x, a.y - b.y, a.z - b.z};
}

Point cross(const Point &a, const Point &b) {
    return {
        a.y * b.z - a.z * b.y,
        a.z * b.x - a.x * b.z,
        a.x * b.y - a.y * b.x
    };
}

Int dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

void solve() {
    int n, k;
    std::cin >> n >> k;
    
    i64 ans = -1;
    i64 set = 0;
    std::vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y, z;
        std::cin >> x >> y >> z;
        a[i] = {x, y, z};
    }
    
    std::set<std::array<i64, 3>> vis;
    vis.insert({0, 0, 0});
    auto check = [&](Point v) {
        i64 g = std::gcd(std::gcd(i64(v.x), i64(v.y)), i64(v.z));
        v.x /= g, v.y /= g, v.z /= g;
        if (vis.count({i64(v.x), i64(v.y), i64(v.z)})) {
            return;
        }
        vis.insert({i64(v.x), i64(v.y), i64(v.z)});
        std::vector<int> p(n);
        std::iota(p.begin(), p.end(), 0);
        std::sort(p.begin(), p.end(),
            [&](int i, int j) {
                return dot(v, a[i]) > dot(v, a[j]);
            });
        auto update = [&]() {
            Point sum;
            for (int i = 0; i < k; i++) {
                sum = sum + a[p[i]];
            }
            i64 res = dot(sum, sum);
            if (res > ans) {
                ans = res;
                set = 0;
                for (int i = 0; i < k; i++) {
                    set |= 1LL << p[i];
                }
            }
        };
        update();
        if (k < n && dot(a[p[k - 1]], v) == dot(a[p[k]], v)) {
            auto d = dot(a[p[k - 1]], v);
            int l = k - 1, r = k + 1;
            while (l > 0 && dot(a[p[l - 1]], v) == d) {
                l--;
            }
            while (r < n && dot(a[p[r]], v) == d) {
                r++;
            }
            for (int i = l; i < r; i++) {
                for (int j = l; j < r; j++) {
                    if (i == j) {
                        continue;
                    }
                    Point u = cross(v, a[j] - a[i]);
                    Point vu = cross(v, u);
                    std::sort(p.begin() + l, p.begin() + r,
                        [&](int i, int j) {
                            auto di = dot(u, a[i]);
                            auto dj = dot(u, a[j]);
                            if (di != dj) {
                                return di > dj;
                            }
                            return dot(vu, a[i]) > dot(vu, a[j]);
                        });
                    update();
                    if (dot(a[p[k - 1]], u) == dot(a[p[k]], u)) {
                        auto d = dot(a[p[k - 1]], u);
                        int l = k - 1, r = k + 1;
                        while (l > 0 && dot(a[p[l - 1]], u) == d) {
                            l--;
                        }
                        while (r < n && dot(a[p[r]], u) == d) {
                            r++;
                        }
                        std::reverse(p.begin() + l, p.begin() + r);
                        update();
                    }
                }
            }
        }
    };
    
    check({1, 0, 0});
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            check(cross(a[j] - a[i], {1, 0, 0}));
            check(cross(a[j] - a[i], {0, 1, 0}));
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                check(cross(a[j] - a[i], a[k] - a[i]));
                check(cross(a[k] - a[i], a[j] - a[i]));
            }
        }
    }
    
    std::vector<int> p;
    for (int i = 0; i < n; i++) {
        if (set >> i & 1) {
            p.push_back(i + 1);
        }
    }
    std::cout << ans << "\n";
    for (int i = 0; i < k; i++) {
        std::cout << p[i] << " \n"[i == k - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}