指挥中心

Grade 100 Open Time Wednesday, 17 June 2020, 10:30 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:30 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:30 PM
Input file city.in Output file city.out

    【题目描述】指挥中心(city)HDU 2121

战斗进行的很顺利,指挥官希望在收复的城市中选择一个做为总部,要求该城市能够连通到其他城市,且道路花费要最少,已知道路都是单向的,请你找出最合适的城市及花费成本。

【输入格式】

输入数据有多组,每种情况有两个整数N和M(N≤1 000,M≤10 000),表示城市数和道路数,城市编号0…N-1,随后M行中,每行有三个整数S,T和C,表示从城市S到城市T有一条路要花费的成本为C。

【输出格式】

如果无解输出“impossible”,否则,输出最低成本和合适的城市号码。如果存在多个适合的城市,选择编号最小的城市。每组答案以一个空行结束。

【输入样例】

3 1

0 1 1

 

4 4

0 1 10

0 2 10

1 3 20

2 3 30

【输出样例】

impossible

 

40 0