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

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

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

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

Đất nước ~ABC~ gồm ~n~ thành phố nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối hai chiều giữa hai thành phố ~u_i~ và ~v_i~, với độ dài là ~x_i~. Thủ đô của ~ABC~ là thành phố ~1~, và có ~k~ chuyến tàu hai chiều, chuyến thứ ~i~ nối từ thủ đô tới thành phố ~s_i~ có độ dài là ~y_i~.

Để tránh gây lãng phí, chính phủ đang muốn xóa đi một số chuyến tàu. Hãy chỉ ra số chuyến tàu nhiều nhất có thể xóa sao cho độ dài của đường đi ngắn nhất từ mọi thành phố tới thủ đô đều không đổi.

Input

• Dòng đầu chứa ba số nguyên ~n,m,k~ ~(n \le 10^5; 1 \le m \le 3 \times 10^5; 1 \le k \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~u_i, v_i, x_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i; 1 \le x_i \le 10^9)~.
• ~k~ dòng sau, mỗi dòng gồm hai số nguyên dương ~s_i~ và ~y_i~. ~(1 \le s_i \le n; 1 \le y \le 10^9)~

Dữ liệu đảm bảo rằng luôn có cách đi từ một thành phố bất kì tới thủ đô, đồng thời có thể có cạnh lặp.

Output

• Gồm một dòng chứa một số là số chuyến tàu có thể bị xóa lớn nhất tìm được.

Sample Input 1

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

Sample Output 1

2

Chow đang đi nghỉ! Với một số tiến bộ công nghệ gần đây, Chow sẽ đi bằng các chuyến bay có công nghệ cao, thậm chí có thể du hành thời gian. Hơn nữa, sẽ không có vấn đề gì nếu hai phiên bản "song song" của Chow gặp nhau.

Trong nước có ~N~ sân bay được đánh số ~1,2,...,N~ và ~M~ chuyến bay du hành thời gian ~(1 \leq N,M \leq 200000)~. Chuyến bay ~j~ rời sân bay ~c_j~ tại thời điểm ~r_j~, và đến sân bay ~d_j~ tại thời điểm ~s_j~ ~(0 \leq r_j,s_j \leq 10^9)~. Ngoài ra, nó phải mất ~a_i~ thời gian cho việc quá cảnh tại sân bay ~i (1 \leq a_i \leq 10^9)~. (Ng hĩa là, nếu Chow đáp chuyến bay đến sân bay ~i~ tại thời điểm ~s~, thì nó có thể chuyển sang chuyến bay rời sân bay vào thời điểm ~r~ nếu ~s+a_i \leq r~. Việc quá cảnh không diễn ra khi Chow đến sân bay.)

Chow bắt đầu tại thành phố ~1~ vào lúc ~0~ . Đối với mỗi sân bay từ ~1~ đến ~N~, thời gian sớm nhất mà Chow có thể đến đó là khi nào?

Input

• Dòng đầu tiên chứa N và M.
• ~M~ dòng tiếp theo mô tả các chuyến bay. Dòng thứ ~j~ trong số các dòng này chứa ~c_j~ , ~r_j~ , ~d_j~ , ~s_j~ theo thứ tự đó. ~(1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9 )~
• Dòng tiếp theo mô tả các sân bay. Nó chứa ~N~ số nguyên cách nhau bằng dấu cách ~a_1,…,a_N~.

Output

In ra ~N~ dòng, dòng thứ ~i~ chứa thời gian sớm nhất Chow có thể đến sân bay ~i~, hoặc ~-1~ nếu Chow không thể đến sân bay đó.

Scoring

Sample

Note

Sample 1

• Chow có thể đi ~3~ chuyến theo thứ tự liệt kê, điều này cho phép nó đến sân bay ~1~ và ~2~ vào thời điểm ~0~, và sân bay ~3~ vào thời điểm ~20~.
• Lưu ý rằng tuyến đường này đi qua sân bay ~2~ hai lần, lần đầu tiên từ thời điểm ~10-11~ và sau đó từ thời điểm ~0-1~.

Sample 2

Trong trường hợp này, Chow có thể bắt chuyến bay ~1~, đến sân bay ~2~ lúc thời điểm 10. Tuy nhiên, cô ấy không đến kịp để bắt chuyến bay ~2~, vì thời gian khởi hành là thời điểm ~10~ và cô ấy không thể quá cảnh trong 1 đơn vị thời gian.

Cảnh sát đang cần sự giúp đỡ của bạn trong việc tìm kiếm nơi trú ở của một tên tội phạm, kẻ đang ẩn náu ở đâu đó trong thành phố gồm n địa điểm khác nhau, được đánh số từ 1 đến ~n~, và có ~m~ đường hai chiều kết nối hai địa điểm khác nhau.

Thông tin từ các người dân trong thành phố, cảnh sát biết được tên tội phạm đã di chuyển từ một địa điểm ~x~ nào đó để đến nơi trú ẩn ~y~ nào đó. Và các nhân chứng có trông thấy hắn xuất hiện ở ~k~ địa điểm ~u_1,u_2,…,u_k~ trên đường đi từ ~x~ đến ~y~ theo thứ tự nào đó mà cảnh sát chưa xác định. Lưu ý rằng tên tội phạm có thể di chuyển từ ~x~ đến ~y~ thông qua các địa điểm khác không có trong ~k~ địa điểm mà các nhân chứng trông thấy. Tuy nhiên, cảnh sát đã phân tích đặc điểm của tên tội phạm này và biết rằng hắn sẽ luôn di chuyển theo đường đi ngắn nhất giữa hai địa điểm ~x~ và ~y~.

Nhiệm vụ của bạn là tìm các địa điểm có thể là ~y~ để giúp cảnh sát có thể nhanh chóng tìm được hắn. Tất nhiên, có thể lời khai của các nhân chứng không đồng nhất dẫn đến không tìm thấy một địa điểm ~y~ nào thỏa mãn.

Input

• Dòng đầu chứa số nguyên ~n,m,k~ (~1≤k≤n≤2⋅10^5,1≤m≤2⋅10^5~)
• Dòng thứ hai chứa ~k~ số nguyên ~u_i~ mô tả những địa điểm tên tội phạm đi qua (~1≤u_i≤n~)
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a,b,c~ mô tả có đường nối trực tiếp giữa hai địa điểm ~a~ và ~b~ có độ dài là ~c~ (~1≤a≠b≤n,1≤c≤10^9~)

Output

• Dòng đầu ghi ra số ~p~ là số địa điểm có thể là ~y~
• Dòng thứ hai ghi ra ~p~ số nguyên là những địa điểm có thể là ~y~ theo thứ tự tăng dần.

Scoring

• 15% số test có ~m=n-1~, và mỗi địa điểm được kết nối trực tiếp với tối đa 2 địa điểm khác.
• 15% số test có ~m=n-1~
• 15% số test có ~n,m≤100~
• 15% số test có ~n,m≤1000~
• 20% số test có ~k≤5~
• 20% số test còn lại không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

4
1 2 4 5

Có ~n~ loại đồ vật, mỗi loại có giá ~a[i]~ và số lượng tối đa ~cnt[i]~.

Bạn cần tìm cách mua hàng nhỏ thứ ~K~, trong đó:

• Một cách mua hàng là một bộ ~b[1], b[2], ..., b[n]~, với ~0 \leq b[i] \leq cnt[i]~.
• Tổng chi phí của một cách mua hàng là: ~sum_{i=1}^{n} a[i] \times b[i]~
• Bạn sắp xếp tất cả các cách mua hàng theo chi phí tăng dần và chọn cách có chi phí nhỏ thứ ~K~.

Input

• Dòng đầu chứa hai số nguyên dương ~n, k~ (~n, k \leq 2 \times 10^{5}~).
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a[i], cnt[i]~ (~a[i] \leq 10^9, cnt[i] \leq 2 \times 10^{5}~).

Output

• In ra chi phí của cách mua hàng nhỏ thứ ~K~.

Scoring

• Subtask 1 (20% số điểm): ~n \leq 20~.
• Subtask 2 (20% số điểm): ~n \leq 100, a[i], b[i] \leq 100~.
• Subtask 3 (20% số điểm): ~cnt[i] = 1~.
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

3 5
2 3
1 2
3 1

Output

3

Note

• Các cách mua hàng hợp lệ có chi phí sắp xếp tăng dần:

  • 0: Không mua gì.
  • 1: Mua 1 món loại 2 (giá 1).
  • 2: Mua 2 món loại 2 (giá 2).
  • 2: Mua 1 món loại 1 (giá 2).
  • 3: Mua 3 món loại 2 (giá 3).
  • 3: Mua 2 món loại 1 (giá 3).
  • 4: Mua 1 món loại 1 và 1 món loại 2 (giá 4).

• Cách mua nhỏ thứ 5 có chi phí 3.

Hôm nay bạn được học về tổ hợp tuyến tính. Trước khi kết thúc buổi học, thầy giáo ra một câu đố như sau:

Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Một số nguyên dương ~x~ được gọi là đẹp nếu tồn tại một bộ ~n~ số nguyên không âm ~v_1, v_2, ..., v_n~ thỏa mãn ~x = a_1 \cdot v_1 + a_2 \cdot v_2 + \cdots + a_n \cdot v_n~.

Gọi ~b~ là tập hợp tất cả các số đẹp sắp xếp theo thứ tự tăng dần. Thầy giáo có ~q~ câu hỏi, mỗi câu hỏi thầy giáo yêu cầu học sinh tìm giá trị của số thứ ~k~ trong dãy ~b~.

Hãy lập trình để giải quyết bài toán.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 3 \cdot 10^5~) — độ dài của dãy ~a~ và ~q~ (~1 \le q \le 3 \cdot 10^5~) — số câu hỏi của thầy giáo.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6, \sum_{i = 1}^n a_i \le 10^6~).

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~k~ mô tả các câu hỏi của thầy giáo ~(1 \leq k \leq 10^9)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho câu hỏi thứ ~i~.

Subtask

• ~5\%~ số test có ~n = 1~.

• ~10\%~ số test khác có ~1 \leq a_1, a_2, ...,a_n \leq 10~.

• ~15\%~ số test khác có ~k \leq 5000~ trong mọi câu hỏi.

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 8
5 3 11
1
2
8
9
6
5
14
23

Sample Output 1

3
5
12
13
10
9
18
27