Concessões de Táxi

A prefeitura de uma cidade emite, ao taxistas, concessões de trabalho. Uma concessão consiste em uma rota que parte do ponto A ao ponto B (e também o caminho contrário, de B até A), sem passar por nenhum outro ponto previamente demarcado. Há uma concessão para cada uma das rotas possíveis entre os $N$ pontos da cidade, e um taxista não está autorizado a passar por uma rota da qual não possua a respectiva concessão.

Um taxista, que já trabalha na cidade, pretende ampliar sua participação profissional. Através de um levantamento informal, ele estimou o lucro diário, em reais, associado a cada concessão. De posse destes dados, ele deseja adquirir novas concessões de modo que possa transportar seus passageiros entre quaisquer dois pontos da cidade e que as rotas escolhidas para aquisição gerem o maior lucro diário possível. Ele deve, porém, manter as concessões que já possui.

Escreva um programa que determine quais rotas devem ser adquiridas de tal modo que o lucro diário seja o maior possível e que o número de aquisições seja mínima. Além disso, após as novas aquisições, o taxista deve ser capaz de transportar seus passageiros entre quaisquer dois pontos da cidade e as concessões já adquiridas devem ser mantidas.

Entrada

A primeira linha da entrada contém o número $N$ ($4\leq N\leq 2\times 10^3$) de pontos da cidade.

As $N(N-1)/2$ linhas seguintes descrevem as concessões, por meio de 4 valores, separados por espaços em branco: o identificador inteiro $I$ ($1\leq I\leq N(N-1)/2$) da concessão, os pontos de partida e chegada $A$ e $B$ ($1\leq A, B\leq N, A\neq B$) e o lucro diário $L$ ($0.01 \leq L\leq 10000.00$) em reais, com duas casas decimais.

A próxima linha contém o número $C$ ($1\leq C\leq \min(100, N/4)$) de concessões que o taxista já possui.

A linha seguinte contém $C$ números inteiros $c_i$ ($1\leq c_i\leq N, 1\leq i\leq C$), separados por espaços em branco, que correspondem aos identificadores das concessões do taxista. Assuma que todas estas concessões são distintas.

Saída

Imprima, em uma linha, o lucro diário máximo possível ao taxista, no formato apresentado no exemplo (antecedido por ‘R$’ e usando a vírgula como separador). Na linha seguinte imprima a quantidade $Q$ de concessões que devem ser adquiridas. Na terceira linha imprima $Q$ identificadores de concessões distintos, separados por um espaço em branco, que atendam as restrições apresentadas.

Caso exista mais de uma escolha de $Q$ concessões possível que leve ao lucro diário máximo, imprima qualquer uma delas, em qualquer ordem.

Exemplo de entrada 1

4
1 1 2 1.32
2 1 3 4.75
3 1 4 0.89
4 2 3 3.33
5 2 4 5.96
6 3 4 2.72
1
3

Exemplo de saída 1

R$ 11,60
2
2 5

Explicação do exemplo 1: o taxista já possui a concessão 3, que lhe rende R$ 0,89 por dia. Ao adquirir as concessões 2 e 5, seu lucro diário passa para R$ 4,75 + R$ 0,89 + R$ 5,96 = R$ 11,60. Além disso, ele consegue levar os passageiros de qualquer origem a qualquer destino, como visto abaixo:

Trecho          Rota (sequência de concessões)

1 <-> 2         3 -> 5
1 <-> 3         2
1 <-> 4         3
2 <-> 3         5 -> 3 -> 2
2 <-> 4         5
3 <-> 4         2 -> 3

Veja que a aquisição da concessão 1, por exemplo, aumentaria o lucro diário, mas violaria a minimalidade do número de aquisições.

Exemplo de entrada 2

4
6 3 4 1.01
1 1 2 2.01
3 1 4 3.01
2 1 3 7.01
5 2 4 4.01
4 2 3 6.01
1
2

Exemplo de saída 2

R$ 17,03
2
4 5

Exemplo de entrada 3

5
1 1 2 13.48
2 2 3 17.77
3 3 4 15.56
4 4 5 11.99
5 5 1 18.78
6 5 3 16.02
7 1 3 15.56
8 4 1 10.01
9 4 2 13.39
10 2 5 15.00
1
8

Exemplo de saída 3

R$ 62,58
3
2 5 6