Parity Constraint Minimum Spanning Tree

Time limit1sMemory limit1024 MB

Summary

Given a weighted connected graph, find the smallest odd and smallest even total cost over all spanning trees, printing -1 when a parity is impossible.

Level: Medium7 of 10
Topics: Minimum spanning tree, Graph, Union-find, Greedy
Solved: No attempts yet

Problem

In 2019, the Yonsei University Optimization Lab suddenly became fond of solving problems with a parity constraint added. Kim Kangsan, a former lab member who has since graduated, also wrote a paper on parity constraints. To commemorate this, Kuklyeol decided to set a parity constraint problem for the Yonsei University Programming Contest.

You are given a graph with $N$ vertices and $M$ undirected edges with costs. The vertices are numbered from 1 to $N$ . Starting from any vertex, there is always a path to every other vertex, and two distinct vertices are connected by at most one edge.

A spanning tree is a subgraph of the given graph that is a tree. Find the minimum odd value and the minimum even value among the possible total costs of spanning trees.

Input

$N$ $M$ $u_1$ $v_1$ $w_1$ . . . $u_M$ $v_M$ $w_M$

Output

Print the minimum odd total cost and the minimum even total cost among the spanning trees. If the corresponding tree does not exist, print -1.

Constraints

2 ≤ N ≤ 100,000.
1 ≤ M ≤ 300,000.
1 ≤ $u_i$ , $v_i$ ≤ N. $u_i$ ≠ $v_i$ . $u_i$ and $v_i$ are the endpoints of the i-th edge.
1 ≤ $w_i$ ≤ 1,000,000,000. $w_i$ is the cost of the i-th edge.
All numbers in the input are integers.

Examples4

Example 1
Input
```
2 1
1 2 1
```
Expected output
```
1 -1
```
Example 2
Input
```
3 2
1 2 3
2 3 3
```
Expected output
```
-1 6
```
Example 3
Input
```
3 3
1 2 3
2 3 3
3 1 2
```
Expected output
```
5 6
```

Example 4

Input

11 23
10 5 832262475
4 10 301084042
4 1 799372953
4 8 689519369
5 2 873313484
6 4 46186948
8 9 388003582
2 7 422044725
5 3 299817881
11 8 779478862
11 5 416526224
11 6 125285000
1 3 566784345
10 6 126434276
11 2 546492450
5 9 914379895
3 7 540663871
7 8 737058872
6 8 932017467
1 9 788517162
11 3 96034563
8 1 113947346
2 10 117057067

Expected output

2301595733 2418304076