Description

那是$1948$年的冬天，南京地下组织的一支小分队决定偷袭老虎桥监狱，救出被困的数百名人员。那时的老虎桥监狱，被$N$层电网围了起来，由内而外，依次编号为$1$,$2$,$\dots$,$N$。第$1$层电网接有高压电。有$M$条高压线，连接了所有电网，其中第$i$条高压线连接了第$a_i$和$b_i$层电网，如果要破坏第$i$条高压线，需要至少动用$T_i$位特工。面对这么多层电网，偷袭小分队犯愁了。至少需要破坏一层电网，否则是无法偷袭成功的。

然而，狡猾的间谍却知道了这件事情，为了破坏偷袭计划，敌人秘密地又增加了一条高压线，不让偷袭小分队的成员发现。

为了能够偷袭成功，不论新增的这一条秘密高压线是连接哪两层电网的，小分队都必须要破坏且仅破坏一条高压线，使得至少有一层电网不通电。注意，对于新增的高压线，我们并不知道需要多少位特工才能成功破坏。现在的问题是，偷袭小分队至少需要多少名特工呢？

决战就在今夜！

Input Format

第一行有$2$个整数，$N$和$M$，分别表示电网层数和高压线个数。 之后$M$行，每行$3$个整数，分别是$a_i$,$b_i$和$T_i$。

Output Format

输出只有一行，包含一个整数，表示最少需要动用的特工人数。 如果计划必然失败，则输出$-1$。

3 2
1 2 1
2 3 2

-1

4 3
1 2 1
1 3 2
1 4 3

3

Hint

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

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

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

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

如果出现在了$2$和$3$之间，则只能破坏$1$和$4$之间的高压线；如果出现在$2$和$4$之间，则只能破坏$1$和$3$之间的高压线；如果出现在$3$和$4$之间，则只能破坏$1$和$2$之间的高压线。

所以，至少需要出动$3$位特工，才能应付所有可能情况。