文理学院程序设计在线练习


远行

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 31   Accepted Submission(s): 23
Problem Description

诺诺开始远行了,好一阵奔波,从绍兴出发,到了厦门,又从厦门到了连城,……,最后到了家,其间乘坐了各种交通工具,出租车、火车、汽车、公交车……好麻烦的一次远行!由于时间关系,诺诺想尽快到家。已知从一个地方到另一个地方,有若干种交通工具,各自要花若干时间(由于等待要花时间的关系,可能乘火车比乘飞机快),请你给出最快到家所花的总时间和各地所用的交通工具。

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。(1<=T<=30)
每组数据有一行输入,首先是1个正整数n(1<=n<=10)表示到家前要经过n个地方,然后是n段交通信息,每段先输入一个整数m(1<=m<=10),表示该段可以使用m种不同的交通工具,然后分别是m种交通工具的状况,每种状况分别由一个字符串和一个整数组成,分别代表交通工具名称(只含英文字母和数字,长度都不超过10)和乘该交通工具到下一个地方所要花的时间(以分钟为单位,不超过24小时),全部的数据之间均以一个空格分隔。
若从一个地方到另一个地方时有多种交通工具所花的时间相同,则优先选择先出现的交通工具。

Output

对于每一组数据,输出最快到家的总时间(以分钟为单位)。
对于每一组数据,输出2行,第一行是最快到家的总时间(以分钟为单位),第二行按交通(输入)顺序逐个输出每个地方乘坐的交通工具名称(之间以一个空格分隔)。

Sample Input
2
2
3
bus1 20 bus2 30 car 10
1
foot 15
2
2
train 200 plane 180
2
foot 10 bus 11
Sample Output
25
car foot
190
plane foot
Author

hlj

Source

绍兴文理学院第五届程序设计竞赛2011/03/27