D. Удаление ребер
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан неориентированный связный взвешенный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Определим длину кратчайшего пути из вершины $$$1$$$ в вершину $$$i$$$ как $$$d_i$$$.

Требуется удалить несколько ребер графа так, чтобы осталось не более $$$k$$$ ребер. Назовем вершину $$$i$$$ хорошей, если после удаления ребер все еще существует путь из $$$1$$$ в $$$i$$$ длины $$$d_i$$$.

Ваша задача — удалить ребра таким образом, чтобы количество хороших вершин было максимально.

Входные данные

В первой строке записаны три целых числа $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$, $$$n - 1 \le m$$$, $$$0 \le k \le m$$$) — количество вершин и ребер в графе, а также максимальное количество ребер, которые могут остаться в графе, соответственно.

Затем следуют $$$m$$$ строк, в каждой содержатся по три целых числа $$$x$$$, $$$y$$$, $$$w$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$, $$$1 \le w \le 10^9$$$), задающие ребро между вершинами $$$x$$$ и $$$y$$$ веса $$$w$$$.

Данный граф связный (любая вершина достижима из любой другой) и простой (не существует петель, и для каждой неупорядоченной пары вершин существует не более одного ребра, соединяющего эти вершины).

Выходные данные

В первой строке выведите $$$e$$$ — количество ребер, которые останутся в графе ($$$0 \le e \le k$$$).

Во второй строке выведите $$$e$$$ различных целых чисел от $$$1$$$ до $$$m$$$ — номера ребер, которые останутся в графе. Ребра пронумерованы в том же порядке, в котором задавались во входных данных. Количество хороших вершин должно быть максимально возможным.

Примеры
Входные данные
3 3 2
1 2 1
3 2 1
1 3 3
Выходные данные
2
1 2
Входные данные
4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5
Выходные данные
2
3 2