Cây khung với đúng K đường thủ đô

Có $n$ thành phố ở Berland, một số cặp thành phố được nối với nhau bằng các con đường hai chiều, mỗi con đường có một trọng số nguyên dương biểu thị độ dài. Thành phố số $1$ là thủ đô. Một con đường được gọi là đường thủ đô nếu một trong hai đầu mút của nó là thành phố $1$.

Công ty MST cần chọn ra một tập gồm đúng $n-1$ con đường sao cho:

1. Sau khi chỉ giữ lại các con đường được chọn, mọi cặp thành phố vẫn có thể đi tới nhau (tức là tập được chọn tạo thành một cây khung của đồ thị).
2. Trong tập được chọn có đúng $k$ đường thủ đô.
3. Tổng độ dài các con đường được chọn là nhỏ nhất có thể khi thoả điều kiện 1 và 2.

Hãy tìm một tập con đường thoả mãn cả ba điều kiện trên, hoặc thông báo không tồn tại.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$ — số thành phố, số con đường, và số đường thủ đô bắt buộc phải có mặt.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$, $w_i$ — con đường thứ $i$ nối hai thành phố $a_i$ và $b_i$ với độ dài $w_i$.

Các con đường được đánh số $1,2,\dots ,m$ theo thứ tự xuất hiện trong dữ liệu vào. Giữa mỗi cặp thành phố có nhiều nhất một con đường. Không có con đường nào bắt đầu và kết thúc tại cùng một thành phố.

Dữ liệu ra

• Nếu không tồn tại tập con đường thoả mãn, in ra một dòng chứa số $-1$.
• Ngược lại, dòng đầu in số $n-1$ — số con đường trong tập được chọn. Dòng thứ hai in $n-1$ chỉ số của các con đường trong tập, cách nhau bởi dấu cách. Các chỉ số có thể in theo thứ tự tuỳ ý.

Nếu có nhiều đáp án tối ưu, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le n\le 5000$
• $0\le m\le {10}^5$
• $0\le k<5000$
• $1\le a_i,b_i\le n$; $a_i\ne b_i$
• $1\le w_i\le {10}^5$

Ví dụ