背景

东汉建安十三年,孙权、刘备联军在长江赤壁一带，大败曹操军队的一次决
战。 曹操败袁绍、 破乌桓， 基本统一北方后， 于建安十三年七月， 自宛挥师南下，
欲先灭刘表，再顺长江东进，击败孙权，以统一天下。九月，曹军进占新野,时
刘表已死，其子刘琮不战而降。依附刘表屯兵樊城的刘备仓促率军民南撤。曹操
收编刘表部众，号称八十万大军向长江推进。刘备在长被曹军大败后，于退军途
中派诸葛亮赴柴桑会见孙权，说服孙权结盟抗曹。
孙权命周瑜为主将，程普为副，率三万精锐水军，联合屯驻樊口的刘备军，
共约五万人溯长江西进，迎击曹军。十一月，孙刘联军与曹军对峙于赤壁。曹操
将战船首尾相连，结为一体，以利演练水军，伺机攻战。周瑜采纳部将黄盖所献
火攻计，并令其致书曹操诈降，曹操中计。黄盖择时率蒙冲斗舰乘风驶入曹军水
寨纵火。 曹军船阵被烧， 火势延及岸上营寨， 孙刘联军乘势出击， 曹军死伤过半，
遂率部北退，留征南将军曹仁固守江陵。联军乘胜扩张战果，孙刘两军分占荆州
要地。话说月黑风高之夜，小Achen又一次离奇穿越来到了大战现场，这一次他又会
遇上什么难题呢？

描述

赤壁决战，曹操在有利形势下，轻敌自负，指挥失误，终致战败。孙权、刘
备在强敌进逼关头，结盟抗战，扬水战之长，巧用火攻，终以弱胜强。
赤壁之战结束之后魏蜀吴三国决定握手求和，但是因为之前四处交战，把道路全
部毁坏了，现在需要重新修路使得三国的国都能够连通.诸葛亮是这个项目的负
责人，Achen身为Tarjan的仰慕者，自然毛遂自荐，但是他太聪明了，对于这种题目都懒得思考了，于是就交给你了。

格式

输入格式

输入一个 T(T ≤ 30)表示 T 组数据
对于每组数据，输入两个正整数 n，m (n<=10000,m<=30000)表示 n 个城
市和 m 条可修建的路。
接下来m行， 每行输入三个整数ai,bi,ci 表示从ai到bi (1<=ai,bi<=n)
的道路需要 ci(1<=ci<=500)的时间进行修建(同一时间只能有一条道路在修建
中)。
接下来输入三个整数 A，B，C(1<=A,B,C<=n，A,B,C互不相等) 分别表示三
国国都所在的城市。

输出格式

对于每组数据，输出一个整数，表示所需要的时间。如果无解输入-1。-

样例输入1

1
4 5
1 2 1
1 3 1
1 4 1
2 3 2
3 4 2
1 2 3

样例输出1

2

后记

**你成功的解决了Achen的问题，可是旅行并没有结束，qq820186690的儿子Achen还会去哪闯祸呢？。

来源

Summer_Wang原创Achen的时空之旅系列1.1