{{{
#!cplusplus
/*
hdu1074
ymc 2008/10/9
题目大意
你n个任务，每个任务完完成的最后期限d和所需的时间c。
如果某个任务的完成时间超过了最后期限d，则要惩罚，惩罚的数值为超过的天数。
求完成这n个任务的最小惩罚数值以及完成的次序。
分析与解题思路：
用n位表示任务的完成状态，对应位上为1表示该任务已经完成，否则表示未完成。
每个状态有三个数据，分别是达到该状态的最小惩罚数值，达到该状态总共所需的时间，已经到达该
状态的最后完成个一个任务。
结构体
struct Status
{
    int reduce; //惩罚时间
    int time;//总共花费时间
    int last;//最后一个完成的任务
};
Status ans[M]表示所有的状态
则状态转移方程为
ans[next].reduce=min{ans[k].reduce+reduce[i]};
其中k为第i个任务未完成，完成的i个任务后，状态k转变为状态next。
*/
#include <iostream>
#include <limits>
using namespace std;
const int N=15;
const int M=65536;
char s[N][110];
int d[N],c[N];
int n;
struct Status
{
    int reduce; //惩罚时间
    int time;//总共花费时间
    int last;//最后一个完成的任务
};
Status ans[M];
void Init()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%s %d %d",s[i],&d[i],&c[i]);
   memset(ans,-1,sizeof(ans));
}
void DP()
{
    ans[0].time=0;
    ans[0].reduce=0;
    int max=(1<<n)-1;
    int next;
    for(int k=0;k<max;k++)
    {
        if(ans[k].reduce==-1)
            continue;
        for(int i=0;i<n;i++)
        {
            int tmp=(k>>i);
            if((tmp&1)==0)//第i个任务未完成
            {
                next=k+(1<<i);
            }
            else
                continue;
            ans[next].time=ans[k].time+c[i]; //完成第i个任务
            tmp=ans[k].reduce;
            if(ans[next].time>d[i])
                tmp+=ans[next].time-d[i];
            if(ans[next].reduce==-1||ans[next].reduce>tmp)
            {
                ans[next].reduce=tmp;
                ans[next].last=i;
            }
        }
        ans[k].reduce=-1;//当前状态以后不会在用到。
    }
}
void Output()
{
    int t;
    t=(1<<n)-1;
    printf("%d\n",ans[t].reduce);
    int out[N];
    int k=0;
    while(ans[t].last>=0)//生成输出序列
    {
        out[k++]=ans[t].last;
        t=t-(1<<ans[t].last);
    }
    for(int k=n-1;k>=0;k--)
        printf("%s\n",s[out[k]]);
}
int main()
{
    int test;
    scanf("%d",&test);
    while(test-->0)
    {
        Init();
        DP();
        Output();
    }
}
}}}