KAMP 02

Cho đồ thị vô hướng liên thông có trọng số G=(V_G, E_G), trong đó V_G là tập các đỉnh của G, E_G là tập các cạnh của G. Đồ thị G có n đỉnh và n-1 cạnh, các đỉnh được đánh số từ 1 đến n

Một đồ thị G’=(V_G’, E_G’) được gọi là đồ thị con của G khi V_G’⊆V_G và E_G’ ⊆ E_G.

Giá trị của một đồ thị là tổng trọng số các cạnh trong đồ thị đó.

Cho tập X (X⊆V_G) gồm k đỉnh. Gọi G’ (đồ thị con của G) là đồ thị liên thông có giá trị nhỏ nhất chứa tập X

Hãy xác định khoảng cách ngắn nhất từ đỉnh u (1≤u≤n) đến G’

Dữ liệu vào: Từ tệp văn bản KAMP02.INP

+ Dòng đầu tiên ghi 2 số nguyên dương n và k (1≤K≤N≤500000)

+ n-1 dòng tiếp theo, mỗi dòng 3 số nguyên u, v, c cho biết c là trọng số của cạnh (u,v). (1≤u, v≤n; 1≤c≤10⁶)

+ Tiếp theo gồm k dòng, mỗi dòng ghi 1 số nguyên là số hiệu của đỉnh thuộc tập X

Dữ liệu ra: ghi vào tệp văn bản KAMP02.OUT

+ Gồm n dòng, dòng thứ u ghi khoảng cách nhỏ nhất của đỉnh u đến G’

Ví dụ: