TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3220
  • Problem
  • P3220ShadowIterator再战啦啦操
    Limits : Time Limit : 10000 MS   Memory Limit : 265536 KB
    Description

    啦啦操队形是一棵很大很大的树,它有n个节点,编号1,2,...,n。每条边都有一个长度。
    ShadowIterator指挥者整个啦啦操队形,但是因为这棵树太大了,ShadowIterator每发布一个命令都要花费很多能量才能传到队形的每个位置。ShadowIterator站在r节点,i节点到r节点的距离为dis(i,r),那么ShadowIterator把信息传到i节点的代价是dis(i,r)。信息之间是相互不影响的,即使两条信息同路,也要各自花费各自的能量。
    ShadowIterator很累了,他当然想少用一些能量。可惜啦啦操队形不能修改,于是他决定通过改变自己站的位置来减少能量消耗。你要找出能量消耗最少的节点每次会消耗多少能量,并按编号由小到大输出这些节点的编号。

    Input Format

    第一行一个数n。
    接下来n-1行,每行三个数x,y,z,表示一条边。

    Output Format

    第一行两个数,第一个数是最少能量消耗,第二个数是节点个数。
    第二行输出这些节点的编号。

    Sample Input

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

    Sample Output

    21 2
    1 4

    Hint

    n<=106
    每条路长度不超过106
    输入数据没有负数。


    Source  感谢nodgd命题并提供数据