U280800 语文考试——公园

数学考试结束后我出去喝了口水语文考试就开始了。我几乎每一题都不会，题题瞎写，最后把作文写完了。

写完以后我就对着非连文本发呆。非连文本上面有一个图，是一个公园，公园里有n-3个亭子和m条街，还有三个大门。我想找到一个亭子，使这个亭子到三个大门的距离之和最短。两个亭子中间不会有重复的街。

第一行两个整数n和m，表示亭子数量和大门数量之和和街道数量。 接下来m行每行三个整数u，v，w，表示街道连接的两个亭子和街道长度 （1，2，3号亭子是大门，答案有可能在大门中其中一个）

输出仅一个整数，表示这个亭子距离三个大门的距离和

对于30%的数据，n