Một công ty cung cấp dịch vụ mạng Internet đang thiết kế hệ thống mạng cho một khu dân cư. Vấn đề thiết kế được mô hình trên đồ thị như sau: Một đồ thị vô hướng có gồm \(n\) đỉnh và \(m\) cạnh, cạnh thứ \(t\) \((1 \leq t \leq m)\) nối đỉnh \(i_t\) đến đỉnh \(j_t\) \((1\leq i_t, j_t \leq n; i_t \neq j_t\) có trọng số là số nguyên dương \(c_{(i_t, j_t)}\), trong đó đỉnh \(1\) và đỉnh \(2\) là hai trạm cung cấp dịch vụ, các đỉnh \(i\) \((3 \leq i \leq n)\) là các trạm sử dụng dịch vụ. Công ty cần cần thiết kế các đường truyền nối, với mỗi đường truyền nối có hai đỉnh đầu cuối là đỉnh \(1\), đỉnh \(2\) và đi qua không quá \(k\) đỉnh sử dụng dịch vụ, cụ thể: Mỗi đường truyền nối xuất phát tại đỉnh \(1\), kết thúc tại đỉnh \(2\) và kết nối không quá \(k\) đỉnh sử dụng dịch vụ; Mỗi đỉnh \(i\) \((3 \leq i \leq n)\) là đỉnh sử dụng dịch vụ thuộc vào duy nhất một đường truyền nối; Độ dài đường truyền nối được tính bằng tổng trọng số các cạnh trên đường truyền nối.

Yêu cầu: Hãy thiết kế các đường truyền nối thỏa mãn điều kiện và tổng độ của các đường truyền nối là càng nhỏ càng nhất.

Input

• Dòng đầu chứa ba số nguyên \(n, m, k\) \((k + 2 \leq n)\);
• Dòng thứ \(t\) \((1 \leq t \leq m)\) chứa ba số nguyên dương \(i_t, j_t, c_{(i_t,j_t)}\), giá trị \(C_{(i_t, j_t)}\) không vượt quá \(10^6\).

Output

• Dòng đầu ghi hai số nguyên \(w\) và \(s\) là tổng độ dài các đường truyền nối và số đường truyền nối được thiết kế;
• \(s\) dòng sau, mỗi dòng mô tả một đường truyền nối có dạng:
• Dòng đầu ghi số \(d\) là lượng đỉnh trên đường truyền nối (bao gồm cả đỉnh \(1\) và \(2\)).
• \(d\) số tiếp theo, mỗi số mô tả đường truyền nối bắt đầu bằng \(1\) và kết thúc tại \(2\)

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n \leq 10\).
• Subtask #2 (\(30\%\) số điểm): \(n \leq 20\).
• Subtask #3 (\(40\%\) số điểm): \(n \leq 50\).

Cách tính điểm:

Có \(20\) test, mỗi test \(5.0\) điểm. Gọi tổng độ dài các đường truyền nối của Ban giám khảo và thí sinh tương ứng là \(w_{GK}\) và \(w_{TS}\), khi đó số điểm bạn đạt được cho mỗi test như sau:

• Nếu \(w_{TS} > 2 x w_{GK}\) thì thí sinh được \(0\) điểm
• Nếu \(w_{TS} < w_{GK}\) thí sinh được \(5\) điểm
• Nếu \(w_{GK} \leq w_{TS} \leq 2 x w_{GK}\) thí sinh được \(5.0 \times \left(1 - \dfrac{w_{TS} - w_{GK}}{w_{GK}}\right)\)

Example

5 7 3
1 3 1
3 2 1
1 4 1
4 5 1
5 2 1
3 4 3
3 5 3

5 2
3 1 3 2
4 1 4 5 2