Xoá cạnh giữ khoảng cách

Cho một đồ thị vô hướng, có trọng số, liên thông gồm $n$ đỉnh và $m$ cạnh. Gọi $d_i$ là độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $i$.

Bạn cần xoá bớt một số cạnh sao cho đồ thị còn lại nhiều nhất $k$ cạnh. Một đỉnh $i$ được gọi là tốt nếu trong đồ thị sau khi xoá vẫn tồn tại một đường đi từ $1$ đến $i$ có độ dài đúng bằng $d_i$.

Hãy chọn các cạnh sẽ giữ lại sao cho số đỉnh tốt là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x_i$, $y_i$, $w_i$ — mô tả cạnh thứ $i$ nối hai đỉnh $x_i$ và $y_i$ với trọng số $w_i$.

Đồ thị đã cho liên thông và đơn (không có khuyên, không có cạnh bội).

Dữ liệu ra

• Dòng đầu in một số nguyên $e$ — số cạnh được giữ lại ($0\le e\le k$).
• Dòng thứ hai in $e$ số nguyên phân biệt từ $1$ đến $m$ — chỉ số (theo thứ tự nhập) của các cạnh được giữ lại. Số đỉnh tốt phải lớn nhất có thể.

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

Ràng buộc

• $2\le n\le 3·{10}^5$
• $1\le m\le 3·{10}^5$, $n-1\le m$
• $0\le k\le m$
• $1\le x_i,y_i\le n$, $x_i\ne y_i$
• $1\le w_i\le {10}^9$

Ví dụ