Задан неориентированный связный взвешенный граф, состоящий из \(n\) вершин и \(m\) ребер. Определим длину кратчайшего пути из вершины \(1\) в вершину \(i\) как \(d_i\).
Требуется удалить несколько ребер графа так, чтобы осталось не более \(k\) ребер. Назовем вершину \(i\) хорошей, если после удаления ребер все еще существует путь из \(1\) в \(i\) длины \(d_i\).
Ваша задача — удалить ребра таким образом, чтобы количество хороших вершин было максимально.
Выходные данные
В первой строке выведите \(e\) — количество ребер, которые останутся в графе (\(0 \le e \le k\)).
Во второй строке выведите \(e\) различных целых чисел от \(1\) до \(m\) — номера ребер, которые останутся в графе. Ребра пронумерованы в том же порядке, в котором задавались во входных данных. Количество хороших вершин должно быть максимально возможным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
1 2 1
3 2 1
1 3 3
|
2
1 2
|
|
2
|
4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5
|
2
3 2
|