#include <iostream>
#define MAXM 1 << 16
#include <vector>
#include <cmath>
#define MAXN 16
#include <string>
using namespace std;
typedef struct {
string obj;
int deadline;
int needday;
}Point;
//所需天数, 前一个状态, 最少损失.
typedef struct {
int nedday;
int fStatus;
int lostScore;
}Node;
Point p[MAXN];
Node dp[MAXM];
bool vist[MAXM];
int n;
void print(int status) {
vector<string> V;
int pre = status;
while(dp[status].fStatus != -1) {
int crr = dp[status].fStatus;
int s = crr ^ pre;
int cc = log(s + 0.00000001) / log(2.0);
V.push_back(p[ cc ].obj);
pre = crr;
status = pre;
}
for(int i = V.size() - 1; i >= 0; -- i) {
cout << V[ i ] << endl;
}
}
void res() {
memset(vist, false, sizeof(vist));
dp[ 0 ].nedday = 0;
dp[ 0 ].fStatus = -1;
dp[ 0 ].lostScore = 0;
int upper = (1 << n) - 1;
for(int j = 0; j < upper; ++ j) {
for(int i = 0; i < n; ++ i) {
int crr = 1 << i;
if((crr & j) == 0) {
//作业i完成时的状态
int curtmp = (crr | j);
//作业i完成时消耗的时间
dp[curtmp].nedday = dp[ j ].nedday + p[ i ].needday;
//作业i完成时超期的时间
int reduce = dp[curtmp].nedday - p[ i ].deadline;
//若不超期
if(reduce < 0) reduce = 0;
//累加前一个状态的超期时间
reduce += dp[ j ].lostScore;
if(vist[curtmp]) {
//该状态访问过
if(reduce < dp[curtmp].lostScore) {
dp[curtmp].lostScore = reduce;
dp[curtmp].fStatus = j;
}
}
else if(!vist[curtmp]) {
//该状态尚未访问
vist[curtmp] = true;
dp[curtmp].lostScore = reduce;
dp[curtmp].fStatus = j;
}
}
}
}
printf("%d\n", dp[upper].lostScore);
/*
for(int i = 0; i <= upper; ++ i) {
cout << i << " " << dp[ i ].fStatus << " " << dp[ i ].lostScore << " " << dp[ i ].nedday << endl;
}
*/
print(upper);
}
int main() {
int test;
cin >> test;
while(test --) {
cin >> n;
for(int i = 0; i < n; ++ i) {
cin >> p[ i ].obj >> p[ i ].deadline >> p[ i ].needday;
}
res();
}
return 0;
}