[献花][花圈]

## 样例输入

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


## 样例输出

3
6


[献花][花圈]