Problem A. Road repairing ≡

Author:Timofey S. Chistyakov
Input file: input.txt   Time limit:5 sec
Output file: output.txt   Memory limit:6 Mb

Statement

A city road network contains N intersections connected with M roads. It is possible to reach any intersection from any other. Before winter started, city major decided to repair some roads in the city, so they wouldn't be totally ruined by spring time.

However, due to magnificent celebration of the city anniversary, city budget is considerably exhausted. That is why city administration wants to repair as little roads as possible. Some roads are already in satisfactory condition and don't need repairing. As to the other roads, the major wants to repair only those that cannot be driven around, even by the bad roads.

Your task is to help the major to obtain the list of the roads that are to be repaired.

Input file format

Input file contains numbers N M, then M triads of numbers ai, bi, ci. Each triad describes one road connecting intersections ai, bi. ci is 1 if the road is in satisfactory condition and 0 otherwise.

Output file format

Output file should contain the number of roads to be repaired, then the list of these roads. Each road should be described by two numbers of connected intersections. The roads should be sorted by first intersection, secondary sorted by second intersection. Within each road description the intersection with less number should come first.

Constraints

1 ≤ N, M ≤ 100000,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
7 8
1 2 0
2 3 1
1 3 0
2 4 1
5 3 0
5 6 1
6 7 0
5 7 0

1 3 5

Problem B. Highways - 2 ≡

Author:A. Klenin, T. Chistyakov
Input file: input.txt   Time limit:2 sec
Output file: output.txt   Memory limit:20 Mb

Statement

There exist a number of small towns in the countryside, which were built after a careful planning. The towns are connected with the highways, which are perfectly straight and go either in north-south or east-west direction. Movement is allowed in both directions on every highway.

Sometimes towns are located at the middle of a highway, not necessarily at its ends. However, a highway always starts at a town and ends at a town.

When two highways cross each other, one of them goes above the other, so drivers don't have to slow down. Therefore it's not possible to get from one highway to another at such crossings. However, if two highways cross at a town, special exits are built, and it's possible to turn from one highway to another.

A highway never has common part with any other highway. In other words, the only locations when two highways may have a common point are towns. Two highways never have more than one common point.

Your task is to calculate the shortest distance that a traveller needs to drive to get from one given town to another.

There are M highways, given as a lines (xi, yi) − (ui, vi). For each highway, either xi = ui or yi = vi. Starting town has coordinates (xs, ys), and destination town is at (xd, yd).

Input file format

Input file contains integers xs ys xd yd M followed by M quartets of integers xi yi ui vi  — coordinates of the beginning and the ending town of each highway.

Output file format

Output file must contain a single number — the length of shortest path between given towns, or −1, if the path does not exist.

Constraints

1 ≤ M ≤ 1000, 0 ≤ xi, yi, ui, vi ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
0 1 14 5
2
0 0 0 10
0 5 15 5
 
18
2 
50 40 90 100
3
7 8 10 8
7 8 7 30
7 8 7 3
 
-1

Problem C. Shortest Spanning Tree ≡

Author:StdAlg
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:16 Mb

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 3
1 2 10
2 3 10
3 1 10
 
20
0.033s 0.005s 11