Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Công ty cung cấp dịch vụ mạng ABC vừa thiết lập một mạng truyền thông bao gồm n nút và m kênh nối trực tiếp hai chiều giữa hai nút. Các nút được đánh số từ 1 đến n, các kênh nối được đánh số từ 1 đến m. Kênh nối thứ i cho phép truyền tin hai chiều từ nút u_i tới nút v_i có độ trễ là c(u_i, v_i) và với chi phí duy trì là 100×c(u_i, v_i). Có không quá một kênh truyền tin từ một nút đến một nút khác. Một đường truyền tin từ nút s đến nút t được biểu diễn dưới dạng một dãy liên tiếp các chỉ số của các nút, xuất phát từ s và kết thúc tại t, trong đó hai nút liên tiếp trong dãy có kênh nối trực tiếp giữa chúng. Độ trễ của đường truyền tin được định nghĩa là tổng độ trễ của các kênh nối trực tiếp trên đường truyền tin đó. Mạng của công ty là liên thông, nghĩa là luôn có đường truyền tin giữa hai máy bất kỳ.

Công ty lựa chọn ba nút x, y, z (1≤ x < y < z ≤ n) làm ba nút nguồn chứa nguồn dữ liệu, các nút còn lại gọi là nút xử lý. Khi đó, mỗi nút xử lý i sẽ chọn đường truyền có độ trễ nhỏ nhất trong số ba đường truyền với độ trễ nhỏ nhất từ ba nguồn x, y hoặc z đến nó làm đường truyền mà theo đó nó sẽ nhận dữ liệu. Ta gọi độ trễ của đường truyền mà theo đó nút xử lý i nhận dữ liệu là độ trễ của nút này và ký hiệu là d_i. Sau một thời gian hoạt động, công ty nhận thấy có thể loại bỏ một số kênh truyền mà các giá trị độ trễ của các nút xử lý là không thay đổi. Vì vậy, công ty muốn tìm cách loại bỏ một số kênh nối sao cho tổng chi phí duy trì các kênh còn lại là nhỏ nhất mà vẫn đảm bảo các giá trị độ trễ của các nút xử lý là không thay đổi.

Yêu cầu: Cho biết thông tin về m kênh truyền tin và k giả định chọn ba nút nguồn. Với mỗi giả định chọn ba nút nguồn, hãy tìm phương án loại bỏ một số kênh truyền tin trong số m kênh truyền tin sao cho tổng chi phí duy trì các kênh còn lại là nhỏ nhất mà vẫn đảm bảo các giá trị độ trễ của các nút xử lý là không thay đổi.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không vượt quá 10 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Mỗi bộ dữ liệu gồm một nhóm dòng có khuôn dạng:

• Dòng thứ nhất chứa ba số nguyên dương n, m, k (n ≤ 500, m ≤ 10000, k ≤ 10000);
• Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương u_i, v_i, c_i cho biết thông tin về kênh truyền tin thứ i (i = 1, 2, ..., m). Giả thiết: u_i ≠ v_i, c_{i ­}≤ 10⁹.

Dòng thứ j trong số k dòng tiếp theo chứa ba số nguyên x­_j, y_j, z_j (1≤ x_j < y_j < z_j ≤ n) mô tả giả định thứ j­­ (j = 1, 2, ..., k).

Output

Với mỗi bộ dữ liệu, ghi ra trên một số dòng, mỗi dòng ghi một số là tổng chi phí nhỏ nhất của phương án tìm được tương ứng với các giả định.

Example

Input:
1
6 6 2
1 2 1
1 3 1
2 3 1
1 4 5 
2 5 5
3 6 5
1 2 3
1 5 6

Output:
1500
700