Có ~n~ thành phố và ~m~ chuyến bay giữa chúng. Nhiệm vụ của bạn là xác định độ dài của tuyến đường ngắn nhất từ ​​Syrjälä đến mọi thành phố.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và chuyến bay. Các thành phố được đánh số ~1,2,\ldots, n~ và thành phố ~1~ là Syrjälä.
• Sau đó, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~ và ~c~: một chuyến bay bắt đầu tại thành phố ~a~, kết thúc tại thành phố ~b~, và độ dài của nó là ~c~. Mỗi chuyến bay là một chuyến bay một chiều.
• Bạn có thể giả định rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Output

• In ~n~ số nguyên: độ dài tuyến đường ngắn nhất từ ​​Syrjälä đến các thành phố ~1,2,\ldots, n~.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le m \le 2 \cdot 10^5~
• ~1 \le a,b \le n~
• ~1 \le c \le 10^9~

Example

Sample input

3 4
1 2 6
1 3 2
3 2 3
1 3 4

Sample output

0 5 2

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

Sample input

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

Sample output

4
1 2 3

Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu khuyến mãi, sử dụng nó có thể giảm một nửa giá của bất kỳ chuyến bay nào trong suốt lộ trình. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó một lần.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và chuyến bay. Các thành phố được đánh số ~1, 2, \ldots, n~. Thành phố ~1~ là Syrjälä, và thành phố ~n~ là Metsälä.
• Sau này, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~ và ~c~: một chuyến bay bắt đầu tại thành phố ~a~, kết thúc tại thành phố ~b~, và giá của nó là ~c~. Mỗi chuyến bay đều là một chiều.
• Bạn có thể giả định rằng luôn luôn có thể đi từ Syrjälä đến Metsälä.

Output

• In một số nguyên: giá của lộ trình rẻ nhất từ Syrjälä đến Metsälä.
• Khi bạn sử dụng phiếu khuyến mãi cho một chuyến bay mà giá tiền của nó là ~x~, giá tiền của nó trở thành ~\lfloor x/2 \rfloor~ (làm tròn xuống một số nguyên).

Constraints

• ~2 \le n \le 10^5~
• ~1 \le m \le 2 \cdot 10^5~
• ~1 \le a,b \le n~
• ~1 \le c \le 10^9~

Example

Sample input

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

Sample output

2

Cho một đồ thị vô hướng, có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Tìm số lượng đường đi ngắn nhất từ ~1~ đến ~n~.

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~u, v, w~, có cạnh trọng số ~w~ nối ~u, v~.

Output

• In ra số lượng đường đi ngắn nhất từ ~1~ đến ~n~, modulo ~10^9+7~..

Điều kiện

• ~1 \le n, m \le 2 \times 10^5~.
• ~1 \le u, v \le n~.
• ~1 \le w \le 10^9~.

Ví dụ

Input:

3 3
1 2 1
2 3 2
1 3 3

Output:

2

Sau khi cướp hết ngân hàng, thì Catalina cùng Claude đã đi tới Liberty City. Chỉ còn CJ ở lại. CJ giờ cũng chẳng biết làm gì, và đi dạo đâu đó chơi. Trong lúc đi dạo, vô tình gặp ông The Truth. Và hai người bắt tay với nhau làm bạn, và cùng nhau tới thành phố San Fierro làm ăn với chiếc xe buýt của ông. Trong lúc đi thì ông chợt nhận ra là ở thành phố này chủ yếu là đường hầm, ông thì chưa đo độ cao chiếc xe ?!!. Và ông đã đưa cho CJ tấm bản đồ San Fierro.

Thành phố San Fierro có ~N~ địa điểm, đánh số từ ~1~ tới ~N~, và ~M~ con đường 2 chiều có hầm, được đánh số từ ~1~ tới ~M~, con đường thứ ~i~ có độ dài là ~L_{i}~, độ cao giới hạn là ~H_{i}~. Xe của ông hiện tại ở địa điểm ~s~, và muốn tới địa điểm ~t~. Và ông quyết định nhờ CJ tìm đường đi mà độ cao đạt được là lớn nhất có thể để đi qua. Trong các đường đi có cùng độ cao lớn nhất, thì ông muốn lấy đường đi ngắn nhất có thể.

Hãy chỉ ra cho CJ con đường thoả mãn điều kiện của ông The Truth. Nếu có nhiều đường đi thoả mãn, in ra một đường đi bất kỳ.

Input

• 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 bốn số nguyên dương ~u_{i},v_{i}, L_{i},H_{i}~ (~1 \leq u_{i},v_{i} \leq N, u_{i} \neq v_{i},1 \leq L_{i},H_{i} \leq 10^{9}~).

Output

• Gồm 2 dòng:
  • Dòng đầu tiên ghi ra độ cao lớn nhất có thể.
  • Dòng thứ hai ghi ra số hiệu trên đường đi tương ứng có độ dài nhỏ nhất theo thứ tự hành trình, bắt đầu từ ~s~ và kết thúc tại ~t~.

Constraints

• ~1 \leq N \leq 10^{5}~, ~1 \leq M \leq 2.10^{5}~

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N \leq 10^{3}~, ~M \leq 2.10^{3}~.
• Subtask ~2~ (~70\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample input

6 6 4 3
1 2 7 10
5 3 3 7
5 1 7 7
5 4 7 3
2 5 5 7
3 6 6 8 

Sample output

3
4 5 3

Cho một đồ thị gồm ~n~ đỉnh và ~m~ cạnh có hướng có trọng số.

Với mỗi đỉnh ~i~, hãy tính độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~3~ số nguyên dương ~u,v,w~ ~(1 \le u, v \le n, u \neq v)~, miêu tả cạnh gồm đỉnh ~u~ nối với đỉnh ~v~ có trọng số ~w~.

Output

• Gồm ~n-1~ dòng, dòng thứ ~i~ in ra độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i + 1~ và quay về đỉnh ~1~. Nếu không có quãng đường nào như vậy thì in ra ~-1~.

Constraints

• ~1 \le n,n \le 2*10^5~.
• ~1 \le w \le 10^9~.

Subtasks

• Subtask ~1~: Nếu tồn tại cạnh ~(u,v,w)~ thì sẽ có cạnh ~(v,u,w)~. ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

5 7
1 4 5
1 5 3
3 5 2
5 4 10
5 1 7
3 2 5
2 1 1

Sample Output 1:

-1
-1
-1
10

Sample Input 2:

2 1
2 1 10

Sample Output 2:

-1