Sau một thời gian dài phát triển, bản đồ xã La Ngâu giờ đây có dạng một đồ thị gồm $N$ địa điểm được nối với nhau bằng $M$ con đường hai chiều. Các địa điểm được đánh số từ $1$ đến $N$. Trong đó, địa điểm $1$ là nơi tọa lạc của trường Tiểu học & Trung học cơ sở La Ngâu, $N-1$ địa điểm còn lại là nhà của các bạn học sinh. Các con đường cũng được đánh số từ $1$ đến $M$. Con đường thứ $i$ có độ dài ~c_i~, kết nối địa điểm ~u_i~ và ~v_i~ ~(u_i \neq v_i)~. Luôn tồn tại đường đi giữa hai địa điểm bất kì trên bản đồ.
Mỗi ngày, các bạn học sinh đều chọn đường đi ngắn nhất từ nhà đến trường để đi học. Nhằm cải thiện đường đi đến trường của các bạn nhỏ, ủy ban xã đã ra quyết định nâng cấp một số con đường sao cho các bạn nhỏ có thể đi đến trường chỉ thông qua những con đường này.
Do không muốn làm ảnh hưởng đến lịch trình của các bạn, điều kiện sau cần thỏa mãn: với mỗi địa điểm $i$ ~(2 \le i \le N)~, đường đi ngắn nhất đến trường (ở đỉnh $1$) thông qua những con đường được nâng cấp là ngắn nhất.
Nhằm giúp ủy ban xã tiết kiệm chi phí, bạn hãy giúp ủy ban xã xác định các con đường cần nâng cấp sao cho tổng độ dài của chúng là nhỏ nhất.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương $N, M$ $(2 \le N \le 10^5, 1 \le M \le 4 \times 10^5)$ - số địa điểm và số con đường trên địa bàn xã;
- $M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên dương ~u_i, v_i~ và ~c_i~ ~(1 \le u_i, v_i \le N,~ ~u_i \neq v_i, 1 \le c_i \le 10^9)~ - mô tả con đường thứ $i$.
Kết quả
Danh sách các con đường cần nâng cấp sao cho với mỗi địa điểm, đường đi ngắn nhất từ địa điểm đó đến trường chỉ đi qua các con đường này là ngắn nhất:
- Dòng đầu tiên gồm số nguyên $K$ $(1 \le K \le M)$ - số lượng con đường cần nâng cấp;
- Dòng tiếp theo gồm $K$ số nguyên cách nhau bởi khoảng trắng - số thứ tự của các con đường. Các giá trị có thể được in theo thứ tự bất kì.
Nếu có nhiều phương án nâng cấp khác nhau cùng thỏa mãn, hãy in ra một phương án bất kì.
Ràng buộc
- Subtask 1 $(30\%)$: $1 \le N, M \le 20$;
- Subtask 2 $(30\%)$: Các con đường có độ dài bằng nhau: ~c_1 = c_2 = \dots = c_N~;
- Subtask 3 $(40\%)$: Không có ràng buộc gì thêm.
Ví dụ 1
Dữ liệu
6 8
6 2 3
6 4 2
6 5 3
1 4 3
1 5 1
2 3 2
2 4 6
4 5 1
Kết quả
5
1 2 5 6 8
Giải thích
Đồ thị của test ví dụ 1 như hình dưới đây, các cạnh được tô màu đỏ thể hiện các con đường được nâng cấp:
Đường đi ngắn nhất đến trường của từng địa điểm như sau:
- Địa điểm 2: $2 \to 6 \to 4 \to 5 \to 1$, độ dài $3+2+1+1 = 7$
- Địa điểm 3: $3 \to 2 \to 6 \to 4 \to 5 \to 1$, độ dài $2+3+2+1+1 = 9$
- Địa điểm 4: $4 \to 5 \to 1$, độ dài $1+1 = 2$
- Địa điểm 5: $5 \to 1$, độ dài $1$
- Địa điểm 6: $6 \to 4 \to 5 \to 1$, độ dài $2+1+1 = 4$
Tổng độ dài các con đường là $9$.
Ví dụ 2
Dữ liệu
4 4
1 2 1
1 4 2
2 3 1
3 4 1
Kết quả
3
1 2 3
Giải thích
Đồ thị của test ví dụ 2 như hình dưới đây, các cạnh được tô màu đỏ thể hiện các con đường được nâng cấp:
Tổng độ dài các con đường là $2+1+1 = 4$
Bình luận