Immediate Delivery
Immediate Delivery
Mike and John are delivery boys of Immediate Delivery. One day they were asked to deliver a lot of packages all over the city.
The transport system of the city they work in consists of junctions and roads connecting these junctions. All roads are bidirectional and all junctions are accessible from each other (directly or indirectly).
Mike and John should visit all the junctions to deliver all packages. They want to split this task into two parts in a way that minimizes the time of the last delivery.
Input
The first line contains two integer numbers n (1 ≤ n ≤ 18) and m, the number of junctions and roads.
The following m lines describe roads. Each line contains three integer numbers: xi and yi (1 ≤ xi, yi ≤ n), the numbers of junctions connected with this road and ti (1 ≤ ti ≤ 1000), the time required to drive it. There is at most one road connecting any two junctions. No road connects a junction to itself.
The office of the Immediate Delivery is placed at the junction number 1.
Output
The first line of the output file must contain the minimal possible time when the last package can be delivered.
The second line must contain the route for Mike: the number of roads p, traveled by Mike and p + 1 numbers of junctions he visited in order they were visited, starting with junction number 1.
The third line must contain the route for John in the same format.
6 6 1 2 10 2 3 10 3 4 5 4 5 10 5 6 20 2 5 10
40 4 1 2 3 4 3 3 1 2 5 6