An quyết định đi du lịch dài ngày. Hiện tại, An đang ở TPHCM và muốn đến Hà Nội. Để đến được đó, anh phải đi qua nhiều thành phố. Có ~n~ thành phố và được kết nối với ~m~ đường hai chiều. TPHCM được dán nhãn là thành phố số 1 và Hà Nội là thành phố số ~n~.

An không chắc chắn về lộ trình từ TPHCM đến Hà Nội nên anh ấy sẽ sử dụng GPS. Nó sẽ dẫn anh đến đích bằng con đường ngắn nhất.

Nhưng An thực sự thích đi du lịch và anh ấy có thể đổ lọ thuốc thần của mình trên bất kỳ con đường nào (ngay cả những con đường mà anh ấy sẽ không đi qua) và tăng chiều dài của nó thêm ~2~ km. Anh ta chỉ có thể đổ nó vào một đường.

Chẳng bao lâu sau, anh nhận ra rằng mình phải nhận phòng ở khách sạn Zora Hà Nội trước buổi trưa nên không thể tăng thêm độ dài của tuyến đường ngắn nhất quá nhiều. Bây giờ, anh ấy muốn biết anh ấy có thể đổ phép thuật của mình vào những con đường nào, để khoảng cách ngắn nhất giữa TPHCM và Hà Nội tăng đúng ~1~ km.

Yêu cầu: Bạn hãy xác định những con đường mà An có thể đổ lọ thuốc ma thuật của mình lên để khoảng cách ngắn nhất giữa thành phố 1 và thành phố ~n~ tăng đúng ~1~ km.

Input

• Dòng đầu tiên chứa số lượng kiểm thử ~t~ (~1 \le t \le 10000~).
• Dòng đầu tiên của mỗi test chứa các số nguyên ~n~ và ~m~ (~2 \le n \le 300000~, ~1 \le m \le \min(300000, n \times (n-1)/2)~).
• ~m~ dòng tiếp theo chứa các số nguyên ~a_i, b_i, w_i~ (~1 \le a_i, b_i \le n, a_i \ne b_i, 1 \le w_i \le 10^9~), nghĩa là tồn tại một con đường nối hai thành phố ~a_i~ và ~b_i~, và chiều dài của nó là ~w_i~. Giữa mỗi cặp thành phố có nhiều nhất một con đường kết nối chúng.
• Tất cả các thành phố đều được kết nối với nhau.
• Tổng của ~n~ và tổng của ~m~ trên tất cả các trường hợp thử nghiệm không vượt quá ~300000~.

Output

• Ở dòng đầu tiên, in số nguyên ~c~, số con đường mà An có thể đổ lọ thuốc ma thuật của mình.
• Dòng thứ hai in ~c~ số nguyên, chỉ số của các con đường theo thứ tự tăng dần.

Sample Input 1

3
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 3
5 6 2
6 7
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
1 6 7

Sample Output 1

2
2 4
0
3
2 4 6