2 图论 (graph)

2.1 问题描述

给定 $n$ 条线段。将每条线段视作图中的一个点，若两条线段有公共点则将他们连边。

你需要删除权值和尽量小的线段使得剩余线段组成的连通块大小均 $\leq m$ 。输出被删除的线段权值和。

2.2 输入格式

第一行，一个整数 $n$。

接下来 $n$ 行，每行三个整数 $L_i,R_i,w_i$。表示第 $i$ 条线段，其中 $w_i$ 为线段权值。

2.3 输出格式

一行，一个整数，表示答案。

2.4 样例 1 输入

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

2.5 样例 1 输出

3

大样例

2.6 数据规模与约定

样例中，一种可能的删除方法是线段 $2$ 和 $5$。本题所有测试点均为 $10$ 分。 $0 \leq m \leq n \leq 2000, 1 \leq Li \leq Ri \leq 10^9, 1 \leq w \leq 10^9$ 。

特殊性质：$m \geq n − 2$ 。