Laser Highways System

All cities in the country are connected by highways. Each highway connects two cities, no two highways intersect outside a city.

The transport scheme in the country uses the notion of the so-called city index. The index of a city is equal to the minimum number of highways a vehicle must traverse to get from the city to the capital. In other words, it is equal to one plus the minimum number of cities, other than the start city and the capital, a vehicle must travel through on its journey from the city to the capital. The index of the capital is 0.

The capital city is economically very important and the highways network is to be upgraded. Some carefully chosen highways will be equipped with quantum laser navigation systems. The upgraded highways are called laser highways. The set of all laser highways is called the laser network. The cost of upgrading a highway is not always the same and it has been calculated for each highway in the country. The cost of the laser network is the sum of upgrade costs of all laser highways in the laser network.

The laser network will be quite costly and very probably it is not going to contain each existing road. On the other hand, the laser network must provide some sensible utility. The authorities make every effort to find a reasonable compromise.

The network must satisfy all three following rules.

• 1. It must be possible to travel via the the laser network from any city in the country to the capital city.
• 2. When a vehicle travels along the laser network from any city to the capital, it must be possible to choose a sequence of laser highways in such a way that the vehicle never enters a city which index is higher than the index of any city the vehicle had left earlier on its journey. (The sequence of indices of the visited cities is non-increasing.)
• 3. The cost of the laser network has to be minimum possible.

Figure 1. A scheme of cities and highways. There are 16 cities and 24 highways. The capital city label is 9, it is highlighted. The laser network, which is highlighted in green, is the least costly laser network with the demanded properties. The scheme illustrates Example 1 below.

The task

You are given the list of highways in the country and the cost of upgrading each highway to a laser highway. Calculate the minimum possible cost of the laser network.

Input

The first input line contains three integers N, M, C. N is the number of cities, M is the number of highways, C is the label of the capital city. All cities are labeled by integers 0, 1, ..., N − 1. The list of all highways is on the next M lines. Each of those lines contains three integers a, b, p separated by space. Integers a and b are labels of two cities connected by a highway and p is the cost of upgrading that highway to a laser highway. The order of the pairs of cities in the list is arbitrary.
The value of N does not exceed 2×10⁴, the value of M does not exceed 2×10⁶. Each upgrade cost is positive and it does not exceed 10³.

Output

The output contains one text line with one integer representing the minimum possible cost of the laser network.

16 24 9
0 1 4
1 2 60
2 3 4
4 5 60
5 6 50
6 7 65
8 9 30
9 10 40
10 11 45
12 13 45
13 14 3
14 15 55
0 4 3
1 5 3
2 6 6
3 7 7
4 8 6
5 9 5
6 10 2
7 11 1
8 12 9
9 13 2
10 14 5
11 15 4

163

7 9 6
0 1 5
2 3 5
4 5 90
4 6 5
5 6 100
0 2 10
2 4 5
1 3 10
3 5 5

120

10 22 6
1 6 16
0 1 15
1 7 17
6 8 10
3 4 10
2 4 13
2 5 14
4 6 13
4 5 19
5 8 18
5 6 13
1 9 18
0 9 11
0 8 15
0 7 18
2 3 17
1 4 10
3 6 12
1 3 11
1 8 12
2 6 16
3 9 13

109

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to the public data set