Huế có ~n~ địa điểm du lịch, các địa điểm đó được đánh số từ 1 đến ~n~ và có ~m~ đường đi hai chiều nối các địa điểm du lịch đó. Khoảng cách từ ~u~ đến ~v~ là ~c~. Giữa hai điểm du lịch có nhiều nhất một đường nối trực tiếp.

Tìm đường đi từ một điểm du lịch hiện tại đến điểm du lịch bất kỳ khác sao cho đường đi là ngắn nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, m~ thỏa ~1 \le n \le 100; 1 \le m \le \frac{n(n-1)}{2}~.

~m~ dòng tiếp theo chứa ba số nguyên là ~u, v, c~ thỏa ~1 \le u, v \le n, 1 \le c \le 10^6~.

Dòng cuối cùng ghi hai số nguyên dương ~s, t~ thỏa ~1\le s, t \le n~ là hai điểm xuất phát và kết thúc của đoạn đường đi cần tìm.

Output

Dòng đầu in ra chiều dài ngắn nhất cần tìm.

Dòng thứ hai đầu tiên ghi số ~x~ là số điểm du lịch trên đường đi cần tìm, tiếp theo ghi ra thứ tự của các điểm du lịch cần đi qua tính từ điểm xuất phát đến điểm kết thúc.

Sample Input

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

Sample Output

4
3 1 2 3