战国初期,各国纷争. 为了保存国土.A国国君会送大量的金银珠宝给B国国君以保证A国不被B国攻打,但是这可能是A国为了骗取B国的信任，然后伺机攻打B国的阴险计划.如果A国赠送珠宝给B国,除了B国不攻打A国之外,保证不攻打B的国家也不会攻打A国.例如:A给B了JYZB,B给了C一些JYZB,那么C既不会攻打B,也不会攻打A. 这里,我们定义一个新概念:同盟国.所谓同盟国就是属于这个同盟国的所有国家都不可能发生战争. 但是,仅仅这样,会造成同盟国之间互相不攻击,但是非同盟国之间会发生战争的情况,这当然不是我们想看到的,而且,在战国时期,还有这样的一个规定,即使A国接受了B国的金银珠宝,但是如果B国不是A国的同盟国,还是不能达成保护协议.但是我们希望最后看到所有国家都不会互相攻击的和谐画面. 所以,我们需要再在国家之间互换人质以求和平.交换人质的两个国家等效于两个国家互相赠送金银珠宝,由于国家之间可能交通不便,所以会造成每两个城市之间可能不能通讯的情况.这时,我们需要找到其中一个国家的同盟国进行中转,同盟国之间人质的押运不会耗费任何经费.如果是非同盟国之间运送,则必须通过道路来运送人质,但是每通过一条道路的时候会需要花费一定的经费来犒赏保卫珠宝的士兵,不同的道路由于路程一样,所以犒赏的金额也有所差异.我们希望耗费的经费的数量可以最少.

第一行:三个整数,N,M,T 表示一共N个城市;之前已经有M对城市之间赠送过珠宝;T条可通行道路. 第二行到第1+M行:每行2个整数,s,t,表示s国曾经给t国赠送过珠宝. 第2+M行到第1+M+T行:每行3个整数,s,t,v,表示从s,t国之间互换人质需要犒赏士兵的费用.

一个整数:最少的耗费.如果无法使得所有的国家都能保持和平状态,则输出'Impossible'

3 0 3
1 3 2
1 2 5
2 3 1

3