oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

unity Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

One man united the warring states

One man dominated all his enemies

That one man is you

And he has realised what a fragmented mass the kingdoms are after the war

The different provinces of the kingdom are connected by bi-directional roads. After the war, many roads have fallen into disrepair, but some still can be used

You can build a some roads between 2 kingdoms, but it will cost you a certain amount of resources.

In order to unite the kingdoms, you will need to connect all the provinces together such that one can move to every other province from any single province using a series of roads [Hint Hint, what is this type of problem?]

However, as you have just ended a war, the opportunity cost of building roads is very high, hence you want to minimise the amount of resources required to do so

Input

The first line of the input contains one integer, the number of provinces n [Provinces are 1 based, i.e. there exist province 1 to n]

The next line contains one integer, the number of working roads, w

The next w lines each contain a pair of integers, wa and wb, where a bidirectional road joins provinces wa and wb

The next line contains one integer, the number of buildable roads, b

The next b lines each contain 3 integers, ba, bb and bc, where a bidirectional road could connect ba to bb at the cost of bc

There will never be more than 1 buildable or working road between 2 distinct provinces

Constraints

n<=10,000, w<=100,000, b<=1,000,000

Output

Output the minimum amount of resources needed to build a road network

If it is impossible to build a road network, output -1

Subtasks

Subtask 1 (15%) w=0, b=n-1, it is guaranteed that it will be possible to build a network

Subtask 2 (55%) w=0, all other above constraints apply

Subtask 3 (30%) Above constraints apply

Sample Testcase 1

Input

3
2
1 2
2 3
1
1 3 10
Output
0

Explanation

You don't need to build anything

Sample Testcase 2

Input

4
2
1 2
2 4
2
2 3 10
1 4 100
Output
10

Explanation

Build the road between provinces 2 and 3

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
115101s32MBMinimum
255101s32MBMinimum
330101s32MBMinimum
4011s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o unity -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.