Công ty cung cấp dịch vụ mạng Alpha 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 vi có độ trễ là \(c(u_i , v_i)\) và với chi phí duy trì là \(100 \times 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\le x < y < z \le 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

Vào từ thiết bị vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên dương \(n, m, k\);
• 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 \ne v_i , c_i \le 10^9\).
• 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\le x_j < y_j < z_j \le n)\) mô tả giả định thứ \(j (j = 1, 2, ..., k)\).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra thiết bị ra chuẩn \(k\) dòng, dòng thứ \(j\) là tổng chi phí nhỏ nhất của phương án tìm
  được tương ứng với giả định thứ \(j\).

Scoring

• Subtask #1 (\(40\%\) số điểm): \(n \le 50, k \le 100\);
• Subtask #2 (\(60\%\) số điểm): \(n \le 500, m \le 10000, k \le 10000\).

Example

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

1500
700