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

input: standard
output: standard

There are N towns and M routes between them. Recently, some new travel agency was founded for servicing tourists in these cities. We know cost which tourist has to pay, when traveling from town i to town j which equals to Cij and time needed for this travel - Tij. There are many tourists who want to use this agency because of very low rates for travels, but agency still has only one bus. Head of agency decided to organize one big travel route to gain maximal possible amount of money. Scientists of the company offer to find such a cyclic path G, when greedy function f(G) will be maximum. Greedy function for some path is calculated as total cost of the path (sum of Cij for all (i,j) - routes used in path) divided by total time of path (similar to Cij). But nobody can find this path, and Head of the company asks you to help him in solving this problem.

There are two integers N and M on the first line of input file (3<=N<=50). Next M lines contain routes information, one route per line. Every route description has format A, B, Cab, Tab, where A is starting town for route, B - ending town for route, Cab - cost of route and Tab - time of route (1<=Cab<=100; 1<=Tab<=100; A<>B). Note that order of towns in route is significant - route (i,j) is not equal to route (j,i). There is at most one route (in one direction) between any two towns.

You must output requested path G in the following format. On the first line of output file you must output K - number of towns in the path (2<=K<=50), on the second line - numbers of these towns in order of passing them. If there are many such ways - output any one of them, if there are no such ways - output "0" (without quotes).

Input

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