Nhân chuyến thi khảo sát đội tuyển HSG Tin học 3HB, HD có dịp về thăm quê, quê hương của HD có ngôi nhà và con đường hai chiều nối chúng, biết rằng:
Giữa hai thành phố bất kỳ đều có đường đi trực tiếp hoặc gián tiếp (đi qua một số con đường trung gian);
Chi phí để di chuyển trên con đường nối thành phố và thành phố là .
Vì ban ngày, HD phải thi HSG tin học, nên HD chỉ có thể đến thăm bạn vào chiều tối, mỗi buổi tối, anh ấy xác định người bạn cần phải thăm đang sống tại thành phố và thành phố . HD muốn đến thăm người bạn trước, sau đó di chuyển đến thăm người bạn . Chi phí về thời gian là rất lớn mà HD thì không được đi quá khuya (vì còn phải nghỉ ngơi để sáng hôm sau còn thi cho tốt và giành giải cao, phần thưởng lớn). Rất may, HD có một người bạn thân là HP, có thể dựng một con đường nối trực tiếp và với thời gian đi là để giúp HD giảm thiểu thời gian di chuyển từ nơi thi, đến thăm bạn sau đó thăm bạn (con đường này chỉ được xây dựng vào buổi tối, và hủy bỏ vào buổi sáng, sau khi HD đã đi thăm bạn xong).
Yêu cầu: Biết rằng HD ở lại quê hương (tại thành phố ) trong buổi tối, bạn hãy tính thời gian đi thăm bạn ít nhất của HD vào mỗi tối? (Không tính thời gian từ quay trở về ).
Dữ liệu vào:
Dòng đầu chứa một số nguyên dương tương ứng là số thành phố;
dòng tiếp theo, dòng thứ chứa hai số nguyên dương và tương ứng có nghĩa có con đường nối thành phố với thành phố và thời gian di chuyển là ;
Dòng tiếp theo chứa số nguyên dương tương ứng là số buổi tối HD ở lại thăm quê;
dòng tiếp theo, dòng thứ ghi ba số nguyên dương thể hiện ở tối thứ HD muốn thăm người bạn ở thành phố , sau đó thăm người bạn ở thành phố và khi xây dựng một con đường tưởng tượng nối thì thời gian di chuyển trên con đường này là .
Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra trên dòng, dòng thứ là thời gian ngắn nhất mà HD có thể đi thăm rồi đến thăm trong truy vấn thứ theo thứ tự.
