网络通路
题号：NC273258
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你是 X 国的总工程师，X 国的 n 个城市之间要架设网络通路，使得每两个国家之间可以通过网络相互到达。为了方便，你希望 X 国架设的网络通路数量最多为 n - 1。然而 X 国的网络通路技术并不成熟，传输速度可以被感知出来，对于每条网络通路，其传输数据所需时间为 d_i，每两条网络通路之间的衔接时间忽略不计。为了使得城市居民使用网络效率最高，你希望对于每两个城市传输时间的和最小，现在你的任务就是求得这个最小值是多少。

输入描述:

第一行两个整数 n, m (1\leq n \leq 16, 1\leq m\leq 200)，接下来 m 行每行两个整数 u_i, v_i, d_i (1\leq u_i, v_i\leq n, 1\leq d_i\leq 100) 表示一条边。不保证没有重边和自环。

输出描述:

第一行一个整数 ans 表示答案，若不存在使得每两个城市都互相到达的方案，输出 -1。
示例1

输入

复制 
4 6
1 2 1
1 3 1
1 4 3
2 3 2
2 4 1
3 4 2

输出

复制 
10