Có \(n\) thành phố và \(m\) công ty xe buýt. Mỗi công ty xe buýt hoạt động ở một số thành phố cụ thể và bán vé với một mức giá cụ thể. Khi mua vé của một công ty xe buýt, bạn có thể di chuyển giữa bất kỳ hai thành phố nào mà công ty đó hoạt động.

Hãy xác định chi phí của tuyến đường rẻ nhất từ Syrjälä đến mọi thành phố.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số thành phố và số công ty xe buýt. Các thành phố được đánh số \(1,2,\dots,n\), và thành phố \(1\) là Syrjälä.

Dòng tiếp theo chứa \(m\) số nguyên \(c_1, c_2,\dots, c_m\): chi phí vé của mỗi công ty xe buýt.

Sau đó có \(m\) cặp dòng mô tả các thành phố của từng công ty xe buýt.

Dòng đầu tiên của mỗi cặp chứa một số nguyên \(k\): số thành phố mà công ty xe buýt hoạt động.

Dòng thứ hai của mỗi cặp chứa \(k\) số nguyên phân biệt \(a_1, a_2,\dots, a_k\): các thành phố mà công ty xe buýt hoạt động.

Bạn có thể giả sử rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Output

In ra \(n\) số nguyên: chi phí tuyến đường rẻ nhất từ Syrjälä đến các thành phố \(1,2,\dots, n\).

Constraints

• \(1 \le n, m \le 10^5\)

• \(1 \le c \le 10^9\)

• \(2 \le k \le n\)

• \(1 \le a \le n\)

• tổng của tất cả các giá trị \(k\) không vượt quá \(2 \cdot 10^5\)

Example

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

0 5 4 4 3