AROAD - Another Road Problem

Problem

Let's say you are given a set of cities (numbered from 1 to n) and possible bidirectional roads between them. You would like to build cheapest road network that will make getting from the capital (which has number 1) to every other city possible, where the cost of the network is just sum of its roads' costs. Seems easy? Well, it certainly would be too easy and boring, so this time you should satisfy one additional constraint: you must consider only networks in which there are at most d roads outgoing from the capital.

Input

First line of input contains number of test cases c (1<=c<=40). Each test case begins with number of cities n, number of possible roads m and maximum degree d (1<=n<=1000, 0<=m<=100000, 0<=d<=100). Then m lines describing roads follow, each of them containing road endpoints x, y and its cost c (1<=x, y<=n, 0<=c<=10000).

Output

For each test case output the cost of building cheapest road network or NONE if it is impossible.

Example

Input:
4
4 5 0
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1000

4 5 1
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1000

4 5 2
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1000

4 5 3
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1000

Output:
NONE
1003
5
4

Added by:gawry
Date:2005-10-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET

hide comments
2011-04-15 19:09:12 :D
n can't be 0, read the constraints. If you can't make a spanning tree with the given limit the answer is NONE. m=0 is no special case needing additional explanation.
2011-01-23 18:31:42 Chairaja Almas Djeni
what if the number of road is 0??
or n=0???
what should be the output??
2010-06-23 05:22:55 tʰɒŋ toŋ ʨĩ
Soenfeah:
Shien veh kuoen "Capital", keuzau tsheh kho tseshiau sandzeon zhiu.
Gheuseu tso "d" chiau, mechiau tu do tse haupe koh pien woen nyoenle koh pien,
pevehku koh sohwo jieu thetsheh.

Last edit: 2010-06-24 09:38:40
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.