Bạn đang crush ai đó... Nhưng bạn nhận ra để cô ấy có thể yêu bạn thì bạn phải tặng cho cô ấy ~n~ món quà. ~n~ món quà sẽ được đánh số từ 1 đến ~n~ trong Pitostore.com. Cửa hàng này chỉ mở bán ~n~ món quà này trong ~m~ ngày, mỗi ngày sẽ bán Combo gồm ~k_i~ món hàng khác nhau (các món quà có thể trùng với Combo trước đó), mỗi Combo sẽ có giá là ~C_i~ đồng. Bạn là một người jàu nên bạn muốn số tiền bạn bỏ ra là ít nhất có thể. Vì thế hãy lập chiến lược trong ~m~ ngày có thể mua đủ ~n~ món quà để tặng cho crush với số tiền là ít nhất.

Input

Gồm ~m+1~ dòng:

• Dòng ~1~: Chứa 2 số nguyên ~n~ và ~m~ ~(n \le 15, m \le 100).~
• ~m~ dòng tiếp theo: số đầu tiên là ~k_i~ ~(k_i \le n)~ là số món quà đang được bán, ~k~ số tiếp theo là số hiệu của món quà, cuối cùng là giá ~c_i~ ~(k_i \le 10^6)~ để mua Combo.

Output

Ghi ra một dòng duy nhất là số tiền ít nhất bỏ ra để mua được ~n~ món quà tặng crush.

Sample Input 1

3 5
2 1 2 5
1 2 10
2 2 3 5
3 1 2 3 18
2 1 3 7

Sample Output 1

10

Sample Input 2

2 2
2 1 2 2
1 1 1

Sample Output 2

2