牛客_BFC_I_Wanna_Go_Home_C++

牛客_BFC_I_Wanna_Go_Home_C++

题目描述

【当前国家正陷入一场严重的内战，国内各大城市被划分为两派，分别支持不同的领导人。作为一名商人，M先生并不关注政治事务，但他清楚地意识到当前局势的严峻性。你的任务是协助他尽快安全返回家中。M先生表示：“为了确保安全，所选择的路线中最多只能包含一条连接不同阵营城市的道路。”请问你能告诉M先生，他从起点返回家园所需的最短时间是多少？

简而言之，M先生需要从编号为1的城市前往编号为2的城市；

地图上包含至少两个城市，各城市之间存在多条长度不一的双向路径；

当前有两位领导人，分别为1号和2号；

编号为1的城市支持领导人1，编号为2的城市支持领导人2；

其余城市则各自支持其中一位领导人；

M先生需从1号城市前往2号城市，并且在途中仅允许有一次阵营转换的机会，即从支持领导人1的城市转移到支持领导人2的城市；

请计算满足条件的最短路径长度。

输入描述

输入数据包含多个测试用例。每个测试用例的第一行是一个整数N（2<=N<=600），表示国家中的城市数量。第二行给出一个整数M（0<=M<=10000），代表道路的数量。接下来的M行是道路的具体信息，每行包含三个整数A、B和T，表示城市A