{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Peter sống ở Expensive City, một trong những thành phố đắt đỏ nhất thế giới. Peter không có đủ tiền để mua xe hơi, và xe buýt ở Expensive City khá tệ, vì vậy anh ấy sử dụng tàu điện ngầm để đi làm. Cho đến nay, tàu điện ngầm rất rẻ: bạn có thể đi bất cứ đâu chỉ với vé $2. Tháng trước, các quản lý quyết định rằng giá vé quá rẻ nên họ đã phát minh ra EFS (Hệ thống Giá vé Đắt đỏ). Với hệ thống này, người dùng chỉ có thể mua vé hàng tháng giữa các ga liền kề, cho phép họ di chuyển giữa các ga này bất kỳ số lần nào. Giá của vé hàng tháng thay đổi giữa các ga, vì vậy quyết định mua vé nào phải được cân nhắc kỹ lưỡng.\n\nVới kế hoạch tàu điện ngầm trước đây, cách rẻ nhất để di chuyển từ Picadilly đến Victoria và Queensway là mua vé hàng tháng Picadilly-Victoria và Queensway-Victoria, với tổng chi phí là $12.\nPeter là một người bán hàng, vì vậy anh ấy cần có thể di chuyển đến bất kỳ phần nào của thành phố. Anh ấy muốn chi tiêu càng ít tiền càng tốt, và đây là nơi bạn xuất hiện. Anh ấy đã thuê bạn để viết một chương trình, cho biết danh sách các ga, giá vé hàng tháng giữa các cặp ga và ga gần nhà Peter nhất, trả về số tiền tối thiểu Peter phải chi tiêu để có thể di chuyển đến bất kỳ ga nào khác. Chương trình này cũng phải trả về giá trị nếu không thể di chuyển từ ga nhà Peter đến tất cả các ga khác, vì trong trường hợp này Peter sẽ bắt đầu cân nhắc sử dụng xe buýt...\n\n### Đầu vào\nĐầu vào bao gồm một số trường hợp kiểm tra. Một trường hợp kiểm tra bắt đầu với hai số nguyên: 1 \u003c s \u003c 400 (số lượng ga) và 0 \u003c c \u003c 79800 (số lượng kết nối) được tách bởi một khoảng trắng. Tiếp theo là s dòng, mỗi dòng chứa tên của một ga tàu điện ngầm. Sau tên của các ga sẽ có c dòng cho thấy các kết nối giữa các ga. Kết thúc trường hợp kiểm tra là một dòng chứa tên của ga mà Peter cần di chuyển đến tất cả các ga khác.\nĐầu vào kết thúc với trường hợp kiểm tra ảo ‘0 0’, không được xử lý.\n\n### Đầu ra\nĐối với mỗi trường hợp kiểm tra, đầu ra sẽ là một dòng chứa một số nguyên, giá vé hàng tháng tối thiểu mà Peter phải trả để di chuyển từ ga đã cho đến tất cả các ga khác, hoặc \"Impossible\" nếu không thể di chuyển đến tất cả các ga.\n\n### Ví dụ\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\nPicadilly\nVictoria\nQueensway\nPicadilly Victoria 2\nQueensway Victoria 10\nQueensway Picadilly 20\nPicadilly\n4 2\nPicadilly\nVictoria\nQueensway\nTemple\nPicadilly Victoria 2\nTemple Queensway 100\nTemple\n0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\nImpossible\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}