Cai fora LAG

Manter uma rede de internet de fibra em funcionamento é uma tarefa muito difícil. Diversos fatores afetam o tempo de resposta de comunicação da rede e cada vez mais fica difícil descobrir o melhor caminho que um pacote pode percorrer, ainda mais que os switches podem fazer parte de empresas diferentes, e os custos de passar um pacote seu por ela pode custar mais caro.

Por isso que na vida real as operadoras tentam não usar a rede das concorrentes para trafegar pacotes. Por exemplo, se você usa internet da NET/CLARO e vai se conectar ao youtube, a sua conexão nunca vai passar por roteadores da VIVO. Pois a VIVO cobraria uma taxa de tráfego de empresa externa, quase que como um pedágio de pacotes.

Para resolver este problema, uma notória equipe de desenvolvedores criou o CAI FORA LAG, uma ferramenta que entende como a rede funciona e sempre descobre o menor caminho (e mais barato) para trafegar os pacotes, isso a qualquer momento da rede.

Para garantir uma economia maior, a CAI FORA LAG ainda instalou um sistema chamado SUPER CONEXÃO, que nada mais é que um super switch (muito caro) com um link muito grande que conecta dois pontos de conexão a uma latência baixa e a um custo muuuito baixo, garantindo assim, uma economia nos gastos da empresa e uma melhora no desempenho da rede dos clientes (essencialmente serve apenas para a CAI FORA LAG economizar dinheiro ao ficar roteando os pacotes dos clientes).

O pessoal do CAI FORA LAG precisa encontrar mais parceiros para conseguir colocar em prática a instalação da SUPER CONEXÃO. E, por isso, precisa saber quanto está economizando ao utilizar este método em lugares específicos.

No desenho abaixo temos uma representação de um pedaço da rede, bem simples, que mostra que as conexões entre os nós da rede de fibra (note que não há direção, pois a rede vai e volta) com um custo associado nas arestas, percebemos que o caminho direto do vértice $0$ para $1$ é de $8$ .

Temos também, na figura, uma rede de SUPER CONEXÃO ligando os vértices $3$ para $1$ a um custo de $-2$ , note que esta conexão é direcionada, ou seja, pacotes podem ser enviados de $3$ para $1$ diretamente, mas o caminho inverso não ocorre.

Então, no desenho acima, se eu quiser enviar um pacote do vértice $0$ para o vértice $2$ , o custo sem SUPER CONEXÃO é $7$ , passando por 0 - 3 - 2 e quando se considera a existência da SUPER CONEXÃO o custo passa a ser $3$ pois o pacote seguiria o caminho 0 - 3 - 1 -2.

Enviar um pacote de $1$ para $0$ o custo é o mesmo sem e com a SUPER CONEXÃO, pois não há vantagens em se utilizar alguma rota que passe pela SUPER CONEXÃO.

A sua tarefa é descobrir o menor custo de operação de envio de pacotes de uma origem a um destino sem considerar a existência dos nós SUPER CONEXÃO e depois considerando a existência deles.

Entrada

A entrada é composta por um único caso de teste. A primeira linha, do caso de teste, possui um número inteiro $V$ ( $2 \leq V \leq 2000$ ) representando a quantidade de switches (vértices) que foram nomeadas de $0$ a $V$ .

A partir da segunda linha, cada linha é composta por quatro inteiros $v$ , $w$ , $c$ e $t$ ( $0 \leq v,w < V$ , $-1000 \leq c \leq 1000$ , $0 \leq t \leq 1$ ), com $v$ e $w$ informando a conexão de fibra entre $v$ e $w$ , $c$ sendo o custo de se utilizar este caminho e $t$ representando o tipo da conexão $0$ para bidirecional e $1$ para SUPER CONEXÃO que é direcional (não existindo o caminho $w$ $v$ com mesmo custo).

Quando $v=w=c=t=0$ , representa que o fim da descrição das conexões e iniciam-se as perguntas da rede.

Para as perguntas cada linha é composta por dois inteiros $o$ e $x$ ( $0 \leq o,x < V$ ) representando a pergunta de qual é o custo para enviar um pacote de $o$ para $x$ .

A entrada termina em EOF.

É garantido que ao menos uma aresta e uma pergunta faça parte da entrada.

Saída

Para cada pergunta você deve imprimir uma única linha contendo:

Dois inteiros $X$ e $S$ , sendo $X$ o custo de enviar pacotes de $o$ para $x$ SEM utilizar a super conexão e $S$ sendo o custo de se enviar pacotes utilizando a SUPER CONEXÃO
Impossibru, quando for impossível calcular o custo com ou sem a SUPER CONEXÃO

Exemplos

Exemplo de Entrada

Saída para o exemplo acima

7 3
8 8
1 1

Exemplo de Entrada

Saída para o exemplo acima

Impossibru
Impossibru
Impossibru

Exemplo de Entrada

Saída para o exemplo acima

7 -5
8 8
1 1

Exemplo de Entrada

Saída para o exemplo acima

7 3
Impossibru

Exemplo de Entrada

Saída para o exemplo acima

Exemplo de Entrada

18
15 7 -938 1
11 0 600 0
13 14 587 0
0 15 274 0
9 6 885 0
12 17 925 0
10 13 40 0
1 5 49 0
13 4 247 0
5 6 78 0
11 12 84 0
1 15 742 0
12 4 962 0
4 9 528 0
17 16 14 0
8 5 120 0
11 1 943 0
7 14 767 0
2 17 673 0
2 14 399 0
11 17 923 0
13 6 587 0
10 5 348 0
0 2 557 0
11 13 793 0
7 3 59 0
6 15 660 0
11 16 596 0
7 6 39 0
14 15 0 0
7 10 87 0
7 8 651 0
14 11 230 0
9 11 944 0
17 15 369 0
12 0 98 0
13 2 956 0
4 16 839 0
13 3 940 0
4 14 222 0
1 14 784 0
15 2 548 0
7 4 869 0
16 3 263 0
11 2 174 0
3 4 582 0
17 8 140 0
15 16 380 0
12 13 582 0
0 1 950 0
1 13 566 0
8 10 37 0
10 9 492 0
14 10 316 0
13 0 327 0
7 17 673 0
11 4 263 0
7 13 19 0
16 6 994 0
16 2 707 0
17 6 310 0
16 8 529 0
12 3 659 0
0 0 0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
1 0
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
2 0
2 1
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
3 0
3 1
3 2
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
4 0
4 1
4 2
4 3
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
5 0
5 1
5 2
5 3
5 4
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
6 0
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 11
10 12
10 13
10 14
10 15
10 16
10 17
11 0
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
11 12
11 13
11 14
11 15
11 16
11 17
12 0
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12 9
12 10
12 11
12 13
12 14
12 15
12 16
12 17
13 0
13 1
13 2
13 3
13 4
13 5
13 6
13 7
13 8
13 9
13 10
13 11
13 12
13 14
13 15
13 16
13 17
14 0
14 1
14 2
14 3
14 4
14 5
14 6
14 7
14 8
14 9
14 10
14 11
14 12
14 13
14 15
14 16
14 17
15 0
15 1
15 2
15 3
15 4
15 5
15 6
15 7
15 8
15 9
15 10
15 11
15 12
15 13
15 14
15 16
15 17
16 0
16 1
16 2
16 3
16 4
16 5
16 6
16 7
16 8
16 9
16 10
16 11
16 12
16 13
16 14
16 15
16 17
17 0
17 1
17 2
17 3
17 4
17 5
17 6
17 7
17 8
17 9
17 10
17 11
17 12
17 13
17 14
17 15
17 16

Saída para o exemplo acima

Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru