BLINNET - Bytelandian Blingors Network

We have discovered the fastest communication medium Bytelandian scientists announced, and they called it blingors. The blingors are incomparably better than other media known before. Many companies in Byteland started to build blingors networks, so the information society in the kingdom of Bytes is fact! The priority is to build the core of the blingors network, joinig main cities in the country. Assume there is some number of cities that will be connected at the beginning. The cost of building blingors connection between two cities depends on many elements, but it has been successfully estimated. Your task is to design the blingors network connections between some cities in this way that between any pair of cities is a communication route. The cost of this network should be as small as possible.

Remarks

  • The name of the city is a string of at most 10 letters from a...z.
  • The cost of the connection between two cities is a positive integer.
  • The sum of all connections is not greater than 232-1.
  • The number of cities is not greater than 10 000.

Input

s [number of test cases <= 10]
n [number of cities <= 10 000]
NAME [city name]
p [number of neigbouring cities to the city NAME]
neigh cost 
     [neigh - the unique number of  city from the main list
      cost - the cost of building the blingors connection from NAME to neigh]
[empty line between test cases]

Output

[separate lines] cost [the minimum cost of building the blingors network]

Example

Input:
2

4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1

3
ixowo
2
2 1
3 3
iyekowo
2
1 1
3 7
zetowo
2
1 3 
2 7


Output:
3
4
Warning: large Input/Output data, be careful with certain languages

Added by:kuszi
Date:2004-06-01
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:PAL

hide comments
2022-09-15 17:49:47
Both prim's and kruskal's work.
2020-07-09 13:41:10
Simple MST Problem
2019-07-31 01:47:15
I don't know what the problem is even I have the right answer
2019-07-25 17:50:08
Sometimes I hate spoj and other users.
Nobody has mentioned , not even the question that there is an extra line of output after we specify number of test cases. I know it's present in the sample input but usually that's just a formatting mistake but not this time. Save WA save frustation. Peace.
2018-07-08 20:11:01
prim's can also work
city names are useless
2018-06-18 14:27:42
got wa using prim's but ac with kruskal
2018-04-25 10:52:22
Simple MST!
2017-08-10 21:52:12 ahmed
classical MST ^_-
2017-06-08 17:45:50
vuhuuu! first mst and dusted in one go.. *_*
2017-04-17 22:19:55
my 69th :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.