Minimum Repair Path

Country C contains \(n\) cities connected by \(m\) bidirectional roads. The cities are numbered from \(1\) to \(n\) and the roads from \(1\) to \(m\). The \(i\)th road connects cities \(u_i\) and \(v_i\) and has length \(w_i\) meters. It is guaranteed that any city can reach any other city via these roads.

The people of Country C love circular trips, but they dislike using too many roads. Therefore, the roads have been constructed in a very special way. More specifically, consider any simple cycle (i.e. a route \(c_1 \rightarrow c_2 \rightarrow \cdots \rightarrow c_l \rightarrow c_1\) with no city repeated except for the starting city) that uses \(l\) roads. If \(l > 3\), then the road network satisfies the following condition: there exist two nonadjacent cities \(c_u\) and \(c_v\) on the cycle (with \(1 \le u < v \le l\), \(v-u \ge 2\) and \(u,v\) are not simultaneously \(1\) and \(l\)) such that there is a direct road connecting \(c_u\) and \(c_v\). In other words, every simple cycle of length greater than three has a chord.

Now Country C plans to renovate a path between two given cities \(s\) and \(t\). During renovation, all roads on the chosen path will be closed. To ensure that every city remains reachable from every other city via the remaining roads, the removed roads must be such that the graph after their removal is still connected.

Your task is to find a simple \(s\)–\(t\) path for renovation such that if all the roads on this path are removed from the graph, the remaining road network is still connected. Moreover, you should choose the path with the minimum total length. If no such path exists, output \(-1\).

Note: A simple path \(v_1, v_2, \ldots, v_k\) (with \(v_1=s\) and \(v_k=t\)) is valid if for every \(1 \le i < k\), after removing all the roads of the path, there exists at least one road (other than the road \(v_i\)–\(v_{i+1}\) from the chosen path) connecting the set \(\{v_1, v_2, \ldots, v_i\}\) and \(\{v_{i+1}, v_{i+2}, \ldots, v_k\}\). This ensures that the removal of the path does not disconnect the graph.

inputFormat

The first line contains four integers \(n\), \(m\), \(s\) and \(t\) \((2 \le n \le 15,\ 1 \le m \le \frac{n(n-1)}{2}\)), representing the number of cities, the number of roads, the starting city and the target city respectively.

Each of the next \(m\) lines contains three integers \(u_i\), \(v_i\) and \(w_i\) \((1 \le u_i, v_i \le n,\ u_i \neq v_i,\ 1 \le w_i \le 10^4)\), meaning that there is a bidirectional road connecting cities \(u_i\) and \(v_i\) with length \(w_i\) meters. There is at most one road between any pair of cities.

outputFormat

If a valid repair path exists, output three lines:

• The first line contains a single integer: the minimum total length of the repair path.
• The second line contains a single integer \(k\): the number of cities in the path.
• The third line contains \(k\) space-separated integers representing the cities on the path in order.

If no valid path exists, output a single line with \(-1\).

sample

2 1 1 2
1 2 10

-1