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

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

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

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 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

Đị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

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~ 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~ 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

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

Bạn muốn đi từ Syrjälä đến Lehmälä bằng máy bay theo tuyến đường có giá tiền nhỏ nhất. Hãy tìm những thành phố mà bạn chắc chắn phải đi qua.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: số thành phố và số chuyến bay. Các thành phố được đánh số ~1,2,…, n~. Thành phố ~1~ là Syrjälä, và thành phố ~n~ là Lehmälä.
• ~m~ dòng tiếp theo mô tả các chuyến bay. Mỗi dòng ghi ba số nguyên ~a, b, c~: có một chuyến bay từ thành phố ~a~ đến thành phố ~b~ với giá ~c~. Tất cả các chuyến bay đều là chuyến bay một chiều.
• Dữ liệu đảm bảo có một tuyến đường từ Syrjälä đến Lehmälä.

Output

• Dòng đầu in một số nguyên ~k~: số thành phố chắc chắn nằm trong tuyến đường. Dòng tiếp theo in ~k~ thành phố được sắp xếp theo thứ tự tăng dần.

Constraints

• ~1\leq n \leq 10^5~
• ~1\leq m \leq 2 ⋅ 10^5~
• ~1\leq a, b \leq n~
• ~1\leq c \leq 10^9~

Example

Sample input

5 6  
1 2 3  
1 3 4  
2 3 1  
2 4 5  
3 4 1  
4 5 8

Sample output

4  
1 3 4 5

Ở một vương quốc nọ có ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Mạng lưới giao thông của vương quốc gồm ~m~ con đường, con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với độ dài đúng bằng ~1~ ki-lô-mét.

Có ~k~ dự án nhà máy điện đang được triển khai, dự án thứ ~j~ sẽ xây một nhà máy điện đặt tại thành phố ~p_j~, cung cấp điện cho tất cả các thành phố nằm trong bán kính ~r_j~ ki-lô-mét (giả sử rằng quãng đường di chuyển trong nội thành là bằng ~0~). Nhà vua đang băn khoăn, những thành phố nào đã được cấp điện, và những thành phố nào chưa được cấp điện? Hãy giúp nhà vua giải quyết bài toán này nhé.

Input

Dòng đầu chứa ba số nguyên ~n~, ~m~, ~k~ (~2 \le n, m \le 2 \times 10^5~; ~0 \le k \le 5 \times 10^5~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~) mô tả con đường thứ ~i~.

~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~p_j~, ~r_j~ (~1 \le p_j \le n~; ~0 \le r_j \le 10^9~) mô tả dự án thứ ~j~.

Output

Gồm một dòng duy nhất chứa một xâu nhị phân gồm ~n~ kí tự, kí tự thứ ~i~ bằng "1" nếu thành phố thứ ~i~ đã được cấp điện, ngược lại kí tự thứ ~i~ bằng "0" nếu thành phố thứ ~i~ chưa được cấp điện.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~r_1 = r_2 = \dots = r_{k - 1} = r_k~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

4 3 1
1 2
1 3
2 4
2 1

Output 1

1101

Input 2

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
6 0
3 1

Output 2

101111

Một nhóm cướp biển có một bản đồ về một vùng biển rộng lớn để chiếm đoạt được kho báu. Đảo mà chúng sống được đánh dấu bằng chữ o. Các tên cướp có thể bắt đầu hành trình của họ ở bất kỳ một trong bốn hướng. Các dòng chảy biển ở vùng biển này di chuyển theo một trong bốn hướng và được đánh dấu như sau: từ phía tây sang phía đông >, từ phía đông sang phía tây <, từ phía bắc sang phía nam v và từ phía nam sang phía bắc ^. Khi các tên cướp đang ở trên một ô có dòng chảy, chúng sẽ di chuyển sang ô khác theo hướng của dòng chảy.

Ô biển lặng được đánh dấu bằng dấu chấm .. Nếu dòng chảy đưa các tên cướp đến một ô biển lặng, hoặc đưa họ ra khỏi bản đồ, hoặc quay trở lại đảo xuất phát, họ sẽ dừng hành trình của mình. Đảo mà các tên cướp muốn đến được đang có kho báu đánh dấu bằng x.

Với việc phải di chuyển theo các dòng chảy, con thuyền của những tên cướp biển này có thể đi vào một vòng xoáy không lối thoát và có thể không đến được hòn đảo đang nắm giữ kho báu. Tuy nhiên, con thuyền của chúng cũng có sức mạnh thần kì: nó có thể đi khác hướng với dòng chảy, có thể tùy ý đi sang một hướng bất kì mà không phải hướng của dòng chảy. Tuy nhiên, nếu sử dụng quá nhiều lần sức mạnh có thể khiến thuyền bị hư hỏng. Nhiệm vụ của bạn là hãy sử dụng ít điểm sức mạnh nhất có thể để đi đến đích.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 2000)~ là kích thước vùng biển.
• ~n~ dòng tiếp theo, mỗi dòng gồm một dãy kí tự o<>v^.x thể hiện dòng chảy hoặc vị trí bắt đầu / kết thúc. Lưu ý có duy nhất một kí tự o và một kí tự x.

Output

Dòng đầu tiên gồm số nguyên dương ~k~ - số lần con thuyền cần sử dụng sức mạnh ít nhất. ~n~ dòng tiếp theo, mỗi dòng gồm dãy ~m~ kí tự, miêu tả một bản đồ mới khác bản đồ ban đầu đúng ~k~ ô mà tại ~k~ ô này, con thuyền sử dụng sức mạnh để có thể đi đến nơi đảo chứa kho báu.

Subtask

• Subtask ~1~ ~(30\%)~: ~3 \le n, m \le 20~.
• Subtask ~2~ ~(70\%)~: Không có điều kiện gì thêm.

Sample Input 1

3 3
>vo
vv>
x>>

Sample Ouput 1

1

Explanation 1

Có thể dùng sức mạnh ở ô ~(3, 2)~

>vo
vv>
x<>

Sample Input 2

4 4
x.v.
.>.<
>.<.
.^.o

Sample Output 2

4

Explanation 2

Một cách sử dụng sức mạnh như sau:

x<<.
.>^<
>.<^
.^.o

Một công ty có ~n~ nhân viên đang trong quá trình tái cơ cấu tổ chức. Sau quá trình này, sơ đồ cấp bậc trong công ty tạo thành một đồ thị dạng cây gồm ~n~ đỉnh, mỗi đỉnh là sếp của tất cả các con của chúng.

Mỗi nhân viên có một danh sách gồm ~k_i~ người họ đồng ý làm sếp trực tiếp của mình. Ngoài ra, mỗi nhân viên cần được tính toán lại lương sao cho lương của mỗi người sếp phải lớn hơn tổng lương của những nhân viên người đó quản lí.

Hãy tìm cách tái cơ cấu lại công ty sao cho tổng lương phải trả cho ~n~ nhân viên là nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số nhân viên trong công ty.
• ~n~ dòng tiếp theo, mỗi dòng bắt đầu bởi số nguyên ~k_i~. Sau đó là ~k_i~ số nguyên dương là danh sách những người được nhân viên thứ ~i~ đồng ý làm sếp của mình.

Output

• Gồm một số nguyên dương là tổng lương phải trả nhỏ nhất.

Subtask

• Subtask 1 ~(20\%)~: ~2 \le n \le 10, \sum{k_i} \le 20~
• Subtask 2 ~(45\%)~: ~2 \le n \le 200, \sum{k_i} \le 200~.
• Subtask 3 ~(35\%)~: ~2 \le n \le 5000, \sum{k_i} \le 10000~.

Sample Input 1

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

Sample Output 1

8

Explanation 1

    3
   / \ 
  4   2
 /
1

Lương của từng người là ~[1, 1, 2, 4]~.