Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0047 - FROZEN ROSE-HEADS

   The winter is coming and all the experts are warning that it will be the coldest one in the last hundred years. Freddy needs to make sure that his garden does not sustain any damage. One of the most important tasks is to make sure that no water remains in his large watering system.

   All the water comes from a central node and is distributed by pipes to neighboring nodes and so on. Each node is either a sprinkler (rose head) with no outgoing pipe or an internal node with one or more outgoing pipes leading to some other nodes. Every node has exactly one incoming pipe, except for the central node which takes the water directly from a well and has no incoming pipe. Every pipe has a valve that stops all the water going through the pipe. The valves are of different quality and age, so some may be harder to close than others.

   Freddy knows his valves well and has assigned a value to each pipe representing the amount of effort needed to close the corresponding valve. He asks you to help him count the minimum effort needed to close some valves so that no water goes to the sprinklers.

Input

   The input contains several test cases. Each test case starts with a line with two integers, the number of nodes n (2 ≤ n ≤ 1 000), and the number of the central node c (1 ≤ c n). Each of the next n − 1 lines represents one pipe and contains three integers, u, v (1 ≤ u, v n) and w (1 ≤ w ≤ 1 000), where u and v are the nodes connected by a pipe and w is the effort needed to close the valve on that pipe. You may assume that every node is reachable from the central node.

Output

   For each test case, output a single line containing the minimum sum of efforts of valves to be closed, such that the central node gets separated from all sprinklers.

Examples

stdin

stdout

1

3  1                               

2  1  5                           

1  3  4                          

7  7                              

7  6  10                        

7  5  10                        

6  4  1                          

6  3  1                          

5  2  1                          

5  1  2                      

9

5


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-27
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.CTU Open 2013.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.