AT_abc022_c.[ABC022C] Blue Bird

高桥君居住的城市有 $N$ 个房屋和 $M$ 条道路。房屋编号为 $1$ 到 $N$ 的整数。高桥君住在 $1$ 号房屋。道路也编号为 $1$ 到 $M$。第 $i$ 条道路连接房屋 $u_i$ 和房屋 $v_i$，长度为 $l_i$ 米，是双向道路。

高桥君要寻找传说中的“幸福的蓝鸟”，据说它藏在城市的某个房屋里。实际上，“幸福的蓝鸟”就在高桥君的家里，高桥君自己也知道这一点。但如果不象征性地去寻找一下，气氛就不够热闹，所以他还是打算制定一个旅行计划。

高桥君打算从自己家出发，访问若干房屋，途中不重复经过同一条道路，最后回到自己家。在旅途中，他计划至少访问自己家以外的 $1$ 个房屋，以增加趣味性。高桥君希望尽快结束这场“闹剧”，因此他认为总路程最短的计划是最优的。

现在给出高桥君所在城市的房屋和道路信息，请你判断高桥君是否能制定出满足上述条件的最优计划。如果可以，请输出他所经过道路长度的最小总和。

输入通过标准输入给出，格式如下：

$N$ $M$
$u_1$ $v_1$ $l_1$
$u_2$ $v_2$ $l_2$
$\vdots$
$u_M$ $v_M$ $l_M$

• 第 $1$ 行包含房屋数量 $N(3 \leq N \leq 300)$ 和道路数量 $M(3 \leq M \leq \frac{N(N-1)}{2})$，以空格分隔。
• 接下来的 $M$ 行中，第 $i$ 行包含第 $i$ 条道路连接的房屋编号 $u_i, v_i(1 \leq u_i < v_i \leq N)$ 以及道路长度 $l_i(1 \leq l_i \leq 10^5)$，以空格分隔。
• 对于 $i \neq j$，至少有 $u_i \neq u_j$ 或 $v_i \neq v_j$ 成立。

如果无法制定出满足条件的最优计划，则输出 $-1$。如果可以，输出最短总路程的长度。输出末尾需换行。

样例解释 1

房屋和道路的分布如下所示：

按 $1, 2, 5, 3, 4, 1$ 的顺序访问的计划是最优的。按 $1, 2, 1$ 的顺序访问的计划由于重复经过了第 $1$ 条道路，不满足条件。

样例解释 2

无法制定出不重复经过同一条道路的旅行计划，因此输出 $-1$。

由 ChatGPT 4.1 翻译