Problem A. Shortest Spanning Tree ≡

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

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

Problem B. SST for sparse graph ≡

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

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, M ≤ 100000 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

Problem C. Topological sorting ≡

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

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number −1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
4 3
1 2
1 3
3 4
 
1 3 2 4
0.136s 0.007s 17