题目描述

见样例

输入格式

见样例

输出格式

见样例

样例

样例 1

输入 # 1

5 2

1 3 1

1 4 10

2 3 20

3 5 20

输出 # 1

21