145. Strange People

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

Once upon a time in one kingdom lives strange people. In this kingdom to travel from city to city there was a taxes. But people don't want to travel cheaper from one place to another. They want to travel from place to place by K-th simple expensive path betwen this cites. Your task is to find how much money they must prepare to go from one given city to another (also given) if they travel using K'th simple expensive path between these two cites. And you must print that path. (if there exist many solutions output any of them) It is guarantee that K'th expensive path between this cites exist. If there is road between city X and Y than there is road between Y and X. Between two cites exists no more than 1 road.

   4 <= N - number of cites <= 100
   M - number od roads
   1 <= taxes bewtween two cites <= 10000
   1 <= K - the K'th expensive path to find <= 500

Input

   N M K
   x y mon |
   x y mon |    ... | M lines
   x y mon |
   xs xe
where xs is start city and xe is end city x and y is pairs of integer that are numbers of two cites and mon is tax between this cites

Output

Z dc
x1 x2 x3 x4 .. xn
where Z is the cost of the K'th expensive path and x1 x2 ... xn is the path dc is number of cites in (x1 x2 x3 ... xn)

Sample Input

  5 10 3
  1 2 6
  1 3 13
  1 4 18
  1 5 35
  2 3 14
  2 4 34
  2 5 17
  3 4 22
  3 5 15
  4 5 34
  1 5

Sample Output

  35 2 
  1 5

Some explanations to Sample Test case:
This are all paths beteen 1 and 5 and their costs
1 2 5 -> 23
1 3 5 -> 28
1 2 3 5 -> 35
1 5 -> 35
1 3 2 5 -> 44
1 4 5 -> 52
1 4 3 5 -> 55
1 3 4 5 -> 69
1 4 2 5 -> 69
1 4 3 2 5 -> 71
1 2 4 5 -> 74
1 2 3 4 5 -> 76
1 2 4 3 5 -> 77
1 4 2 3 5 -> 81
1 3 4 2 5 -> 86
1 3 2 4 5 -> 95

if there exist q or more paths with equal cost than if first of them is K'th expensive path then some of others q - 1 cites is (K + 1)'th expensive path and so on.. Example in Sample test paths 1 2 3 5 and 1 5 have equal cost so 3'th expensive path is 35 and 3'th expensive path may be 1 5 or 1 2 3 5 and 4'th expesnive path is 35 and 4'th expensive path may be 15 or 1 2 3 5