### 问题描述 原神 $3.0$ 版本马上就要到来，须弥地图即将开放。 神秘少女纳西坦答应荧，如果她能以最快的速度点亮须弥所有的传送点，就可以和小吉祥草王贴贴。 岩之魔神摩拉克斯非常好心地送来了须弥的地图，地图上有 $n$ 个传送点，分别标注为 $1\sim n$，**旅行者荧可以在已经点亮的传送点之间瞬间传送**。 特别地，当旅行者来到须弥的范围中时，传送点 $1$ 会自动点亮，并开始计时。 见多识广的风之魔神温迪告诉旅行者，须弥地形复杂，有沙漠，有雨林，有的道路非常难走，并且很容易迷失方向，或者因体力不支而倒下。最终，他们讨论出了 $m$ 条可以行走的路径（路径是双向的），第 $i$ 条路径连接传送点 $ u_i,v_i$，需要花费 $w_i$ 分钟到达。 最后，旅行者向雷之魔神借用了她的人偶作为计算机，但她根本不会使用。 旅行者向你寻求帮助。作为回报，她会给你三份甜甜花酿鸡。 但是你觉得旅行者给的太少，决定只告诉她最快多快能点亮须弥，不告诉她具体应该怎么走。 ### 输入格式 输入第 $1$ 行包含两个正整数$ n$ 和 $m$，分别表示地图传送点的个数以及边数。 第 $2\sim m+1$ 行每行包含三个整数 $u_i,v_i,w_i$，表示 $u_i$ 和 $v_i$ 之间有一条需要走 $w_i$ 分钟的路。 ### 输出格式 输出一行，这一行只包含一个整数，表示最快多少分钟能够点亮须弥所有传送阵；如果永远无法点亮全部传送阵的话，输出 $-1$。 ### 样例输入 ```text 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 ``` ### 样例输出 ```text 7 ``` ### **说明/提示** 对于所有评测数据，$1\leq n \leq 10^5，n−1 \leq m \leq 10^6，1\leq u,v\leq n，0\leq w\leq 10^3$。 **注意：本题数据量较大，$C/C++$ 语言建议使用 $scanf$ 读入。**