Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC).
×

No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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.

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.

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

1 2 1

1 3 2

3 4 2

2 4 2

Output

2 3

2 1 2

2 3 4

2 1 2

2 3 4

Author: | Sergey Simonchik |

Resource: | Petrozavodsk Summer Training Sessions 2004 |

Date: | August 25, 2004 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2019 17:28:37 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|