COCI '19 Contest 5 #4 Putovanje

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Little Fabijan loves bars and travels. He wishes to drink beer coffee in each of the N towns in his country conveniently numbered from 1 to N. The towns are connected via N1 bidirectional roads such that each town is reachable from any other town by traversing some of the roads. Fabijan decided to drink coffee in every town in order from town number 1 to town number N. Therefore, he starts from town number 1 (where he drinks his first coffee) and travels to town number 2 for his next cup of coffee. During that travel, he might pass through a number of different towns but he won't make a coffee stop in those towns. After drinking coffee in town 2, he will proceed to travel to town 3, and so on until he finally reaches town N where he will drink his last coffee.

In order to traverse a certain road, he needs to have a valid ticket. The i-th road can be traversed if you have either a single-pass ticket which costs Ci1 euros or a multi-pass ticket which costs Ci2 euros. For each road, Fabijan can decide to buy a single-pass ticket each time he needs to traverse that road or he might opt to buy a multi-pass ticket once.

Write a program that computes the smallest number of euros Fabijan needs to spend on tickets in order to successfully complete his travels.

Input

The first line contains an integer N (2N200000) from the task description.

In i-th of the next N1 lines there are four integers Ai,Bi,Ci1,Ci2 (1Ai,BiN,1Ci1Ci2100000) which represent that towns Ai and Bi are connected with a road with ticket prices Ci1 and Ci2.

Output

In a single line output the smallest cost of travel.

Scoring

Subtask Score Constraints
1 20 2N2000
2 25 Each town will be directly connected with at most two other towns.
3 65 No additional constraints.

Sample Input 1

Copy
4
1 2 3 5
1 3 2 4
2 4 1 3

Sample Output 1

Copy
10

Explanation for Sample Output 1

Fabijan first travels from town 1 to town 2 and it is optimal for him to buy a multi-pass ticket (5 euros) for the road which connects them. Then he travels from town 2 to town 3 via town 1. He already has a multi-pass ticket that takes him from 2 to 1 and he buys a single-pass ticket from town 1 to town 3 (2 euros). On his travels from town 3 to town 4 he buys another single-pass ticket that takes him from town 3 back to town 2 (2 euros) and after that buys a single-pass ticket that takes him from town 2 to town 4 (1 euro). In total, he spent 5+2+2+1=10 euros.

Sample Input 2

Copy
4
1 4 5 5
3 4 4 7
2 4 2 6

Sample Output 2

Copy
16

Sample Input 3

Copy
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3

Sample Output 3

Copy
11

Comments

There are no comments at the moment.