T423196 「YAC Round 3」星屑幻想 Stardust Reverie

 > 东风夜放花千树，更吹落，星如雨。

幻想乡人间之里烟花晚会马上就要开始啦，可偏偏在这个时候天空下起了朦朦细雨。即便是在这雾雨的天气，人们仍然期待着烟花能够在夜空中绽放。 突然，你想到有一位普通的魔法使——雾雨魔理沙，能够使用符卡 魔符 「Stardust Reverie」 星屑幻想 来放出绚丽多彩的火花。然而，这个时候雾雨魔理沙却不在人间之里，不过幸运的是，你在人间之里碰巧遇见了爱丽丝，于是你拜托爱丽丝去寻找雾雨魔理沙。 雾雨魔理沙不是在魔法森林采蘑菇就是在红魔馆大图书馆看书。幻想乡由 $N$ 个地点和 $M$ 条双向道路组成，并且 **任意两个地点之间有且仅有一条通路**。一条双向道路可以由 $(u, v, w)$ 表示，其中 $u, v$ 表示道路连接的两个地点，$w$ 表示经过双向道路的所需的时间。 人间之里在地点 $C$，魔法森林在地点 $A$，红魔馆在地点 $B$ 。爱丽丝很清楚 $A, B, C$ 的具体编号位置，但是身为人类的你并不知道具体位置。 为了尽快找到雾雨魔理沙，爱丽丝会遵循以下规则： - 爱丽丝会从 $C$ 出发。如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 更近，那么爱丽丝会先去 $A$ 找魔理沙，如果没有在 $A$ 找到，则再去 $B$ 找； 反之亦然。 - 爱丽丝总是沿着两个地点之间唯一的通路行走。 由于你不知道 $A, B, C$ 的具体位置，所以你只能委托爱丽丝。请你计算出 **最坏情况下** 爱丽丝 **需要多长时间** 找到魔理沙。

第一行是两个整数 $N$ 和 $M$，分别表示幻想乡地点总数和双向道路总数。 接下来 $M$ 行，每行输入三个整数 $u_i, v_i, w_i$，表示第 $i$ 条道路的信息，其中 $u_i, v_i$ 表示道路连接的两个地点编号，$w_i$ 表示经过这条双向道路所需的时间。 道路信息不会重复给出。

输出一行一个整数表示最坏情况下找到魔理沙需要的时间。

对于所有测试数据，$3 \le N \le 2\times 10^5$，$1 \le u_{i},v_{i} \le N$，$1 \le w_{i} \le 10^{9}$。