P12530 [AOJ] Content Delivery
普及
题目描述

Example

Input

3 2
1 2 1
2 3 2
1 10 100

Output

320

输入格式

见题面

输出格式

见题面

样例输入
3 2 1 2 1 2 3 2 1 10 100
样例输出
320