Parity Constraint Shortest Path

Interview

Time limit1sMemory limit1024 MB

Summary

Given an undirected weighted graph, find for every vertex the minimum cost of an even path and of an odd path from vertex 1, allowing repeated vertices and edges.

Level: Medium6 of 10
Topics: Graph, Shortest path, Dynamic programming, Heap
Solved: No attempts yet

Problem

In 2019, the optimization lab at Yonsei University went through a phase of solving problems with a Parity Constraint suddenly added to them, and alumnus Kim Gangsan wrote a paper on Parity Constraints as well. To commemorate this, Gukryeol decided to set a Parity Constraint problem for the Yonsei University programming contest.

You are given a graph with N vertices and M undirected weighted edges. Every vertex is numbered from 1 to N. From any vertex there is always a path to any other vertex, and between any two distinct vertices there is at most one edge.

You start at vertex 1 and want to travel to the other vertices. You may pass through vertices or edges you have already visited again, and each time you pass through an edge its cost is added. For convenience, define the cost of a path as the sum of the costs of the edges that make up the path. If the cost of a path is odd, call it an odd path; if even, an even path. For each vertex, find the cost of the minimum-cost odd path and the cost of the minimum-cost even path from vertex 1.

Input

The input is given as follows.

N M
u1 v1 w1
. . .
uM vM wM

Output

Print N lines. On the i-th line, print the cost of the minimum odd path and the cost of the minimum even path from vertex 1 to vertex i, separated by a space. If such a path does not exist, print -1.

Constraints

2 ≤ N ≤ 100,000.
1 ≤ M ≤ 300,000.
1 ≤ ui, vi ≤ N. ui ≠ vi. ui and vi are the endpoints of the i-th edge.
1 ≤ wi ≤ 1,000,000,000. wi 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 0
1 -1
```
Example 2
Input
```
3 2
1 2 3
2 3 3
```
Expected output
```
-1 0
3 -1
-1 6
```
Example 3
Input
```
3 3
1 2 3
2 3 3
3 1 3
```
Expected output
```
9 0
3 6
3 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

1633663809 0
1031595251 1089051244
566784345 1066879464
799372953 834290856
1366697345 866602226
845559901 788103908
1511095969 851006218
1523810225 113947346
1780982121 501950928
971994177 914538184
970844901 662818908