题目描述

输入格式

输出格式

样例

样例输入 1

3 3 
1 2 1 
3 1 2 
3 2 3

样例输出 1

1

样例输入 2

7 9 
1 2 8 
1 3 3 
2 3 6 
4 2 7 
4 5 1 
5 6 9 
6 7 3 
7 4 2 
4 6 2

样例输出 2

3