Minimum Toll Cost

The king wishes to visit all his castles while paying the minimal total toll. The kingdom consists of n castles connected by m bidirectional roads. Each road has an associated toll cost. You are given an integer n (the number of castles), an integer m (the number of roads), and an integer s (the starting castle). Following this, there are m lines each describing a road with three integers u, v, and w, representing a road between castle u and castle v with toll cost w.

Your task is to choose a subset of these roads forming a spanning tree (i.e. connecting all castles) such that the total toll cost is minimized. Mathematically, if T is a spanning tree with edges e and tolls w_e, you must minimize:

If it is impossible to connect all the castles (i.e. the graph is disconnected), output -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m s
u1 v1 w1
u2 v2 w2
... 
um v m w m

where the first line contains three integers: n (number of castles), m (number of roads), and s (starting castle). Each of the next m lines contains three integers u, v, and w indicating there is a road between castle u and castle v with toll cost w.

outputFormat

Output a single integer on standard output (stdout) which is the minimum total toll cost that connects all the castles. If it is impossible to visit all castles, output -1.

4 4 1
1 2 4
2 3 3
3 4 2
4 1 1

6