题目背景

滨江老城的防洪调度站由 $N$ 层环形闸门拱卫，闸门之间靠输电缆联动。抢险队要在暴风雨夜潜入检修，而守夜人可能悄悄加挂一条临时缆线。这是一场供电与断电的博弈。

题目描述

调度站被 $N$ 层闸门围了起来，由内而外，依次编号为 $1$,$2$,\dots,$N$。第 $1$ 层闸门接有高压电。有 $M$ 条输电缆，连接了所有闸门，其中第 $i$ 条输电缆连接了第 $a_i$ 和 $b_i$ 层闸门，如果要剪断第 $i$ 条输电缆，需要至少动用 $T_i$ 名队员。面对这么多层闸门，抢险队犯愁了。至少需要让一层闸门断电，否则行动无法成功。

然而，守夜人察觉到了风声，为了阻止行动，他秘密地又加挂了一条临时缆线，不让抢险队发现。

为了行动成功，不论新增的这条临时缆线连接哪两层闸门，抢险队都必须要剪断且仅剪断一条输电缆，使得至少有一层闸门断电。注意，对于新增的临时缆线，我们并不知道需要多少名队员才能剪断它。现在的问题是，抢险队至少需要多少名队员呢？

输入格式

第一行有 $2$ 个整数，$N$ 和 $M$，分别表示闸门层数和输电缆个数。

之后 $M$ 行，每行 $3$ 个整数，分别是 $a_i$,$b_i$ 和 $T_i$。

输出格式

输出只有一行，包含一个整数，表示最少需要动用的队员人数。

如果行动必然失败，则输出 $-1$。

样例

3 2
1 2 1
2 3 2

-1

4 3
1 2 1
1 3 2
1 4 3

3

提示

对于 $30\%$ 的数据，$N \leq 200$，$M \leq 250$。

对于 $70\%$ 的数据，$N \leq 50000$，$M \leq 100000$。

对于 $100\%$ 的数据，$N \leq 500000$，$M \leq 1000000$，$T_i \leq 100000$。

对于第二组样例，新增的缆线只有可能出现在 $2$ 和 $3$，$2$ 和 $4$ 或 $3$ 和 $4$ 之间。

如果出现在了 $2$ 和 $3$ 之间，则只能剪断 $1$ 和 $4$ 之间的输电缆；如果出现在 $2$ 和 $4$ 之间，则只能剪断 $1$ 和 $3$ 之间的输电缆；如果出现在 $3$ 和 $4$ 之间，则只能剪断 $1$ 和 $2$ 之间的输电缆。

所以，至少需要出动 $3$ 名队员，才能应付所有可能情况。