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

input: standard
output: standard

There are N towns in the country, connected with M railroads. All railroads are one-way, the railroad system is organized in such a way that there are no cycles. It's necessary to choose the best trains schedule, taking into account some facts.
Train path is the sequence of towns passed by the train. The following conditions must be satisfied.
1) At most one train path can pass along each railroad.
2) At most one train path can pass through each town, because no town can cope with a large amount of transport.
3) At least one train path must pass through each town, or town economics falls into stagnation.
4) The number of paths must be minimal possible.
Moreover, every railroad requires some money for support, i-th railroad requires c[i] coins per year to keep it intact. That is why the president of the country decided to choose such schedule that the sum of costs of maintaining the railroads used in it is minimal possible. Of course, you are to find such schedule.

The first line of input contains two integers N and M (1<=N<=100; 0<=M<=1000). Next M lines describe railroads. Each line contains three integer numbers a[i], b[i] and c[i] - the towns that the railroad connects (1<=a[i]<=N; 1<=b[i]<=N, a[i]<>b[i]) and the cost of maintaining it (0<=c[i]<=1000). Since the road is one-way, the trains are only allowed to move along it from town a[i] to town b[i]. Any two towns are connected by at most one railroad.

On the first line output K - the number of paths in the best schedule and C - the sum of costs of maintaining the railroads in the best schedule.
After that output K lines, for each train path first output L[i] (1<=L[i]<=N) - the number of towns this train path uses, and then L[i] integers identifying the towns on the train path. If there are several optimal solutions output any of them.

Input

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