Immediate Delivery#2378
Mike and John work for Immediate Delivery. One day, they were asked to deliver a lot of packages across the whole city.
The city's transportation system consists of junctions and roads connecting them. All roads are bidirectional, and every junction can be reached from any other (directly or indirectly).
Mike and John must visit all the junctions to deliver all packages. They want to divide the task into two parts so that the delivery time of the last package is minimized.
The first line contains two integers (1 \le n \le 18) and — the number of junctions and the number of roads.
Each of the next lines describes a road with three integers: x_i and y_i (1 \le x_i, y_i \le n) — the junctions connected by the road, and t_i (1 \le t_i \le 1000) — the travel time for that road. No two junctions are connected by more than one road. No road connects a junction to itself.
The office of Immediate Delivery is located at junction number .
The first line must contain the minimal possible time by which the last package can be delivered.
The second line must contain Mike's route: the number of roads traveled by Mike, and the numbers of the p + 1 junctions he visited in the order they were visited, starting from junction .
The third line must contain John's route in the same format.
Example 1