The Windy Eulerian Circuit

San Bytecisco is a beautiful coastal town formed by a set of small, densely populated islands numbered from \(1\) to \(n\). Several pairs of islands are connected by bridges that support bidirectional road traffic. Each bridge may be traversed in either direction, but the opposing wind speed – which makes crossing tiring – depends on the direction. In other words, for a bridge connecting islands \(u\) and \(v\), crossing from \(u\) to \(v\) is associated with a constant wind speed \(w(u,v)\), and crossing from \(v\) to \(u\) with a (possibly different) wind speed \(w(v,u)\>.

The islands and bridges form an undirected Eulerian graph (i.e. every island is reachable from every other island and every island has even degree). Byteasar and Bytie want to take a bike trip starting and ending on island \(1\) that uses every bridge exactly once – an Eulerian circuit. However, they wish to choose not just any Eulerian circuit but one where the maximum opposing wind speed encountered along the route is minimized. Formally, if the chosen route traverses bridges in an order and if \(c_i\) is the wind speed experienced on the \(i\)th crossing, they want to minimize \(\max_i \{c_i\}\>.

Your task is to find such a least tiresome route. The input provides the number of islands and bridges, followed by a description of each bridge. Each bridge is given as four integers: u v a b meaning that for that bridge, crossing from island \(u\) to island \(v\) has wind speed \(a\) and from island \(v\) to island \(u\) has wind speed \(b\). It is guaranteed that an Eulerian cycle exists. Output the minimum possible maximum opposing wind speed and one corresponding Eulerian circuit (listed as a sequence of island numbers starting and ending with 1).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of islands and bridges). Each of the next \(m\) lines contains four integers \(u\), \(v\), \(a\) and \(b\) representing a bridge connecting islands \(u\) and \(v\) with wind speeds \(a = w(u,v)\) and \(b = w(v,u)\) respectively. There is at most one bridge between any pair of islands. It is guaranteed that the underlying undirected graph is connected and Eulerian.

outputFormat

Output two lines. The first line should contain a single integer – the minimized maximum opposing wind speed. The second line should contain the Eulerian circuit as a sequence of island numbers (separated by spaces), starting and ending at island \(1\).

sample

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

5
1 2 3 1