Given $n, m$, and $m$ conditions of the form $a_{x_i} \ge a_{y_i} + a_{z_i}$ ($1 \le i \le m$), determine whether there exists a set of positive integers $(a_1, a_2, \dots, a_n)$ that satisfies all conditions such that $a_1 + a_2 + \dots + a_n \le 10^9$. If such a set exists, output the minimum value of $a_1 + a_2 + \dots + a_n$; otherwise, output $-1$.

Input

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \times 10^5$).

Each of the following $m$ lines contains three integers $x_i, y_i, z_i$, representing a constraint $a_{x_i} \ge a_{y_i} + a_{z_i}$ ($1 \le x_i, y_i, z_i \le n$).

Output

Output a single integer representing the answer.

Examples

Input 1

5 2
1 2 3
3 4 5

Output 1

8

Note

The solution with the minimum sum is $(3, 1, 2, 1, 1)$, which gives a sum of $8$.