Thành phố ABC có ~n~ khu dân cư với ~m~ đường nối 2 chiều đảm bảo liên thông toàn thành phố. Đường đi thứ ~i~ nối 2 khu ~u_i~ và ~v_i~ có thể di chuyển 2 chiều với độ dài ~w_i~. Tại thành phố này, công ty VTEL hoạt động trong lĩnh vực kinh doanh dịch vụ viễn thông luôn chiếm thị phần rất lớn trong lĩnh vực của mình. Công ty vừa ký hợp đồng cung cấp dịch vụ ~k~ khách hàng VIP, khách hàng thứ ~i~ sinh sống ở khu dân cư ~p_i~ (~1≤p_i≤n~ ~∀i=1,2,…,k~). Để đảm bảo hỗ trợ kỹ thuật, giải quyết sự cố, công ty chọn ~k~ nhân viên chăm sóc khách hàng, mỗi nhân viên sẽ phục vụ một khách hàng. Nhân viên thứ ~i~ đang sinh sống tại khu ~q_i~ (~1≤q_i≤n~ ~∀i=1,2,…,k~) và khi nhận được thông tin sự cố sẽ di chuyển từ chỗ ở theo đường đi ngắn nhất qua các khu trung gian tới khu dân cư nơi mà khách hàng của mình đang sinh sống để chăm sóc hỗ sợ. Quãng đường di chuyển bên trong khu dân cư là không đáng kể.

Yêu cầu: Hãy giúp ban lãnh đạo công ty phân công ~k~ nhân viên, mỗi nhân viên hỗ trợ chăm sóc một khách hàng để quãng đường di chuyển của người phải đi xa nhất là ngắn nhất.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~n,m,k~ (~n≤300,m≤5000~)

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên dương ~u_i~, ~v_i~,~w_i~ xác định thông tin đường nối giữa 2 khu ~u_i~ và ~v_i~ (~u_i,v_i≤n;w_i≤10^6~ ~∀1≤i≤m~). Dữ liệu đảm bảo giữa 2 khu đi chỉ có 1 đường nối duy nhất.

• Dòng tiếp theo chứa ~k~ số nguyên ~p_1,p_2,…,p_k~ xác định nơi ở của ~k~ khách hàng.

• Dòng cuối cùng chứa ~k~ số nguyên ~q_1,q_2,…,q_k~ xác định nơi ở của ~k~ nhân viên. (~1≤p_j,q_j≤n~ ~∀j:1≤j≤k~)

Output

• Dòng đầu tiên ghi số nguyên ~d~ là quãng đường di chuyển của nhân viên phải đi xa nhất theo cách phân công từ nơi ở tới chỗ khách hàng được phân công.

• Dòng thứ hai chứa ~k~ số nguyên ~x_1~ ~x_2~ ~x_3~…~x_k~ (~1≤x_i≤k~) với ~x_i~ là số thứ tự của khách hàng mà nhân viên thứ ~i~ được phân công hỗ trợ.

Scoring

Chấm điểm: Bạn cần đưa ra đủ 2 dòng với cấu trúc như trên. Gọi ~d_0~ là đáp án của ban tổ chức. Điểm của bạn nhận được sẽ là ~d_0/d~ số điểm của test đó. Bạn chỉ được điểm trong trường hợp ~k~ số nguyên đưa ra thể hiện cách phân công phù hợp với giá trị ~d~.

Sample Input 1

5 6 2
1 2 4
3 5 2
5 4 1
3 4 5
3 2 4
1 4 6
1 2
3 5

Sample Output 1

7
2 1

Sample Input 2

5 6 3
1 2 4
3 5 2
5 4 1
3 4 5
3 2 4
1 4 6
1 2 3
3 5 2

Sample Output 2

4
2 3 1

Notes

Giải thích: Ở ví dụ thứ nhất, nhân viên số 1 (khu 3) sẽ chăm sóc khách hàng số 2 (khu 2) với quãng đường 4. Nhân viên số 2 (khu 5) sẽ chăm sóc khách hàng số 1(khu 1) với quãng đường 7.

Ở ví dụ thứ hai, nhân viên số 1 (khu 3) chăm sóc khách hàng số 2 (khu 2) với thời gian di chuyển là 4, nhân viên số 2 (khu 5) chăm sóc khách hàng số 3 (khu 3) với thời gian di chuyển là 2, nhân viên số 3 (khu 2) chăm sóc khách hàng số 1 (khu 1) với thời gian di chuyển là 4.