Заданий неорієнтований зважений граф з \(N\) вершин та \(M\) ребер, кожне ребро якого біле або чорне.
Знайдіть мінімальний каркас графа, в якому буде рівно \(K\) білих ребер.

Формат вхідних даних

В першому рядку три цілих числа \(N,M,K\) (\(1 \le N \le 50000\)) , (\(0 \le M \le 100000\)).
В наступних \(M\) рядках міститься по 4 цілих числа \(V1,V2,W,C\) опис ребер. Ребро кольору \(C\) і вагою \(W\) з'єднує вершини \(V1,V2\).
ВЕРШИНИ НУМЕРУЮТЬСЯ ПОЧИНАЮЧИ З 0
\(C=0\) - позначає біле ребро, \(C=1\) - чорне

Формат вихідних даних

Виведіть вагу мінімального каркаса, який містить рівно \(K\) білих ребер (гарантується, що розв'язок завжди існує)

Приклад вхідних даних-1

2 2 1 
0 1 1 1 
0 1 2 0

Приклад вихідних даних-1

2

Приклад вхідних даних-2

15 30 5
0 1 83 1
1 2 71 1
2 3 43 1
3 4 19 0
4 5 96 1
5 6 42 1
6 7 5 0
7 8 10 1
8 9 38 1
9 10 56 1
10 11 6 0
11 12 90 0
12 13 54 0
13 14 30 1
5 6 80 0
11 13 48 1
13 5 67 1
10 2 96 0
7 8 40 1
5 6 63 1
6 4 33 0
8 6 64 1
1 8 43 0
1 2 53 0
3 11 40 1
9 4 13 0
7 12 79 1
8 4 96 1
10 13 66 0
5 1 49 1

Приклад вихідних даних-2

480