Để phát triển thêm thị trường du lịch trong nước, Công ty du lịch Xuyên Việt muốn lập ra một tuyến đường du lịch mới từ Hà Nội đến Hồ Núi Cốc tỉnh Thái Nguyên. Sau thời gian dài thảo luận, Công ty đã đưa ra một phương án chọn tuyến đường này như sau.

Hãy tưởng tượng rằng quanh tuyến đường lên Hồ Núi Cốc có N địa điểm được đánh số từ 1 (là Hà Nội) đến N (là Hồ Núi Cốc) và M con đường. Mỗi con đường nối hai địa điểm và có một chỉ số xếp hạng về vẻ đẹp. Độ dài của tuyến đường được tính bằng số con đường đi qua, và vẻ đẹp của tuyến đường được thể hiện bằng dãy chỉ số xếp hạng của các con đường theo thứ tự đi qua từ Hà Nội đến Hồ Núi Cốc.

Trong đó, dãy số (a1, a2, ..., an) được gọi là có thứ tự từ điển nhỏ hơn (b1,b2,...., bn) khi và chi khi tồn tại vị trí k (1 ≤ k ≤ n) sao cho ak < bk và ai = bi với mọi 1 ≤ i < k.

Yêu cầu: Em hãy viết chương trình xác định tuyến đường du lịch từ Hà Nội đến Hồ Núi Cốc sao cho độ dài của tuyến đường đó là ngắn nhất và thứ tự từ điển của dãy chỉ số xếp hạng thể hiện vẻ đẹp của tuyến đường đó là nhỏ nhất.

Dữ liệu: Vào từ file văn bản BROAD.INP Dòng đầu ghi hai số N và M (1 ≤ N ≤ 10^5,1 ≤ M ≤ 10^6)

Mỗi dòng trong M dòng tiếp theo ghi ba sốa,, bị và rị thể con đường hai chiều nối hai địa điểm ai và bị có chỉ số xếp hạng là r, (1 ≤ ai, bi ≤ N, 1 ≤ ri ≤ 10^9). Có thể có nhiều con đường nối hai địa điểm.

Kết quả: Ghi ra file văn bản BROAD.OUT gồm hai dòng:

Dòng đầu ghi số L là độ dài tuyến đường ngắn nhất từ Hà Nội đến Hồ Núi Cốc.

Dòng thứ hai chứa L số thể hiện chỉ số xếp hạng của các con đường trên tuyến đường ngắn nhất và có thể thứ tự từ điển nhỏ nhất. Các số trên cùng một dòng cách nhau một dấu cách trống.

Input:

4 5
1 2 2
1 3 3
2 4 3
3 4 1
3 1 1

Output:

2
1 3