TICHPX Cho Khiêm một bài toán về đồ thị tuy nhiên Khiêm học dốt nên không thể giải được.

Bạn hãy giúp Khiêm nhé!

Cho một đồ thị có hướng có trọng số đơn giản với n đỉnh và m cạnh.cạnh thứ i là (\(Ai\),\(Bi\)) và có trọng số \(Ci\)

Tìm cây khung nhỏ nhất có hướng có gốc là đỉnh S (có nghĩa là tất cả các đỉnh phải đi được từ S).

INPUT:

Dòng đầu nhập vào n,m,S: số đỉnh, số cạnh, đỉnh S

Tiếp theo nhập vào m dòng, đỉnh a, đỉnh b, trọng số c

OUTPUT:

In ra tổng trọng số của các cạnh trong MST được định hướng. \(Pi\) là mẹ của đỉnh \(i\) hay \(Ps\) = S

Giới hạn:

1 ≤ n ≤ 2e6

n-1 ≤ m ≤ 2e6

0 ≤ S < n

0 ≤ \(Ai\),\(Bi\) < n

\(Ai\) != \(Bi\)

(\(Ai\),\(Bi\)) != (\(Ai\),\(Bi\)) (i!=j)

0 ≤ \(Ci\) ≤ 1e9

Tất cả các đỉnh có thể đạt được từ đỉnh S

Ví dụ:

INPUT:

4 4 0
0 1 10
0 2 10
0 3 3
3 2 4

OUTPUT:

17