Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKBUILD - Phát triển Quốc gia

Vua Peaceful vừa khai hoang một vùng đất để lập ra đất nước Peace, lúc đầu chỉ có N thành phố (được đánh số từ 1 đến N) và không có con đường nào.

Vua Peace chọn ra K thành phố đặc biệt để làm trung tâm kinh tế và K thành phố này phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì thế nhà vua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho K thành phố đặc biệt đó vẫn liên thông.

Bạn được biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn một số con đường để xây dựng để theo đúng ý nhà vua biết rằng luôn tồn tại ít nhất một phương án xây dựng đường sao cho K thành phố đặc biệt liên thông.

Input

- Dòng đầu tiên ghi 3 số nguyên dương N, M, K. (M là số con đường có thể xây dựng).

             (1 <= N <= 100;       1 <= M <= 10000;      2 <= K <= 7)

- Dòng thứ hai ghi K số nguyên là số hiệu của K thành phố đặc biệt.

- M dòng tiếp theo, mỗi dòng ghi 3 số nguyên u, v và c với ý nghĩa muốn xây dựng một con đường hai chiều nối trực tiếp giữa 2 thành phố u và v thì chi phí là c. ( 1 ≤ c ≤ 1000000 )

 

Output

Gồm 1 dòng duy nhất là tổng chi phí nhỏ nhất để xây dựng hệ thống đường.

Example

Input:

6 7 3
1 2 3
1 2 10
1 4 1
4 2 2
2 3 10
5 2 3
6 3 1
5 6 4 Output:

11
6 7 3
1 2 3
1 2 10
1 4 1
4 2 2
2 3 10
5 2 3
6 3 1
5 6 4

Được gửi lên bởi:Alex & Friends
Ngày:2012-02-04
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:base on THREE and QBBUILD (vn.spoj.pl)

hide comments
2015-11-07 11:51:36
đa đồ thị @@
2015-05-24 10:50:57 Stupid Dog
bài QBBUILD test yếu nên AC, còn bài này thì chỉ 95
2012-09-09 01:25:17 ptt
WA-test là gì nhỉ?
2012-06-03 01:01:15 Math Error
host oi, post test len dum dag biet cho nao sai ma sua
2012-03-25 05:43:18 xyz
Test 1 là test vd ở trên hay là test chấm của bài này?

Edit: test 1 là test chấm của bài

Last edit: 2012-04-28 02:46:44
2012-02-25 08:16:33 ASUS K43SJ
5 WA-test-1
Kết quả này là gì vậy???

Edit: Được 5 điểm trên toàn bộ test, sai test 1

Last edit: 2012-02-27 02:18:20
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.