题目描述

我们有$n$个盒子和$m$个球(编号都从$1$开始)，目前，球$i$在$A_i$盒子中。

接下来，对于每次操作，你可以执行以下几个操作中的一个：

• 选择一个装有两个或更多球的盒子，从中拿出一个球，把它放入另一个盒子当中
• 由于球都是易碎的，因此，你总共不能移动球$i$超过$C_i$次。

你现在的目标是对于每个$i$，将球$i$放入盒子$B_i$中。请确定这个目标是否可以实现，如果可以，则输出最少需要操作的次数，如果不可以，则输出-1。

输入格式

第一行输入两个数字$n,m$，表示盒子和球的数量。

接下来$m$行，每行三个数字$A_i,B_i,C_i$，表示第$i$个球最初始的位置，需要到达的目标位置，能够最多移动的次数。

输出格式

如果有解，则输出最少需要操作的次数，如果无解，则输出-1.

样例 1

输入

3 3
1 2 1
2 1 1
1 3 2

输出

3

样例 2

输入

2 2
1 2 1
2 1 1

输出

-1

样例 3

输入

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

输出

6

样例 4

输入

1 1
1 1 1

输出

0