Một ngày, OG Loc đã mời CJ dự một buổi tiệc rap của anh ta. Và hôm nay buổi tiệc sẽ diễn ra, nhưng CJ vì mải mê công việc, mà khi nhìn vào đồng hồ và lịch thì … CJ mới chợt nhớ ra về bữa tiệc của OG Loc. Mà còn khoảng \(2\) tiếng nữa là buổi tiệc rap của OG Loc sẽ diễn ra.

CJ nhìn vào bản đồ trong vùng. Bản đồ đấy gồm \(N\) ngôi nhà, đánh số từ \(1\) tới \(N\) và \(M\) con đường hai chiều nối hai ngôi nhà. Ngôi nhà của CJ có số hiệu là \(s\), ngôi nhà có bữa tiệc của OG Loc có số hiệu là \(t\). Vì không muốn tới trễ nên CJ quyết định tìm đường đi ngắn nhất từ nhà của mình tới buổi tiệc tại ngôi nhà của OG Loc và sẽ di chuyển theo đường đi đó.

Input

• Gồm \(M + 1\) dòng:
• Dòng đầu tiên chứa bốn số nguyên dương \(N\), \(M\), \(s\), \(t\) \((1 \leq s, t \leq N, s \neq t)\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số \(u_i\), \(v_i\), \(c_i\) thể hiện có đường hai chiều nối hai ngôi nhà \(u_i\) và \(v_i\), và độ dài là \(c_i\) (\(u_i \neq v_i\)).

Output

• Ghi ra hai dòng:
• Dòng đầu tiên ghi ra độ dài đường đi ngắn nhất.
• Dòng thứ hai là số hiệu trên đường đi ngắn nhất tìm được theo thứ tự di chuyển, bắt đầu từ \(s\) và kết thúc ở \(t\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 2.10^3\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 2.10^5\)

Example

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

4
1 2 3