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

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

Cho một ma trận lưới ~n * m~, các ô vuông được thể hiện bởi chữ số. Từ một ô vuông có thể đi sang ~4~ ô kề cạnh. Viết chương trình tìm đường đi từ ~(x,y)~ đến ~(u,v)~ có tổng các ô chữ số là nhỏ nhất.

• ~(i, j)~ là ô hàng ~i~ cột ~j~.
• Ký tự ~G~ là ô ~(x, y)~.
• Ký tự ~R~ là ô ~(u, v)~.

Input

• Dòng đầu tiên: Hai số nguyên dương ~n~ và ~m~
• ~n~ dòng tiếp theo: Mô tả ma trận lưới.
• Giới hạn: ~n, m \le 1000~

Output

• Độ dài đường đi.

Sample Input

3 3
323
G9R
018

Sample Output

8

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

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

Định nghĩa ~f(x)~ là tổng các chữ số của số nguyên ~x~. Cho số nguyên ~k~, hãy tìm giá trị ~f(x)~ nhỏ nhất có thể khi xét các số nguyên dương ~x~ chia hết cho ~k~.

Input

• Gồm một số nguyên ~2 \le k \le 100000~.

Output

• In ra giá trị ~f(x)~ nhỏ nhất.

Sample Test

Input:

6

Output:

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

Bạn dự định đi từ Syrjälä đến Lehmälä bằng máy bay. Bạn muốn tìm câu trả lời cho các câu hỏi sau:

• giá rẻ nhất của một lộ trình như vậy là bao nhiêu?
• có bao nhiêu lộ trình với giá rẻ nhất? (chia lấy dư cho ~10^9 + 7~)
• số lượng chuyến bay tối thiểu của một lộ trình với giá rẻ nhất là bao nhiêu?
• số lượng chuyến bay tối đa của một lộ trình với giá rẻ nhất là bao nhiêu?

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à Lehmä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~: có một chuyến bay từ thành phố ~a~ đến thành phố ~b~ với giá ~c~. Tất cả chuyến bay đều là chuyến bay một chiều.
• Bạn có thể giả định rằng có một lộ trình từ Syrjälä đến Lehmälä.

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

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

Sample output

5 2 1 2