该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

考古学家发现了一个长度为 $N$ 的神秘数字序列 $A_1, A_2, \dots, A_N$。 虽然我们不知道具体的数值，但我们可以通过购买“线索”来推断。 已知：前缀和 $S_0 = 0$。 黑市上有 $M$ 条线索出售，第 $i$ 条线索的形式为 $(L_i, R_i, C_i)$，表示只要支付 $C_i$ 的金币，就可以知道区间 $[L_i, R_i]$ 内所有数字的和（即 $S_{R_i} - S_{L_i-1}$ 的值）。 通过逻辑推理（例如：知道 $[1, 5]$ 的和 以及 $[1, 2]$ 的和，就能算出 $[3, 5]$ 的和），我们希望求出序列中每一个位置的数值。 请计算：至少需要花费多少金币，才能确定整个序列 $A$ 的所有数值？

输入格式

第一行两个整数 $N, M$，表示序列长度和线索数量。 接下来 $M$ 行，每行三个整数 $L, R, C$，表示一条线索。

输出格式

输出一个整数，表示最小花费。如果无法推断出整个序列，输出 Impossible。

输入输出样例 #1

输入

3 4
1 1 10
2 2 10
3 3 10
1 3 5

输出

25

数据范围

$1 \le N \le 1000$，$1 \le M \le 10000$。