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 00 para 11 é de 88.

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

Pequeno exemplo de conexão

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

Enviar um pacote de 11 para 00 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 VV (2V20002 \leq V \leq 2000) representando a quantidade de switches (vértices) que foram nomeadas de 00 a VV.

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

Quando v=w=c=t=0v=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 oo e xx (0o,x<V0 \leq o,x < V) representando a pergunta de qual é o custo para enviar um pacote de oo para xx.

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:

Exemplos

Exemplo de Entrada

4
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
0 0 0 0
0 2
1 0
2 1
Saída para o exemplo acima
7 3
8 8
1 1

Exemplo de Entrada

4
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
2 0 -5 1
0 0 0 0
0 2
1 0
2 1
Saída para o exemplo acima
Impossibru
Impossibru
Impossibru

Exemplo de Entrada

4
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
0 2 -5 1
0 0 0 0
0 2
1 0
2 1
Saída para o exemplo acima
7 -5
8 8
1 1

Exemplo de Entrada

5
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
0 0 0 0
0 2
0 4
Saída para o exemplo acima
7 3
Impossibru

Exemplo de Entrada

10
6 3 820 0
6 1 270 0
1 0 160 0
9 0 489 0
3 4 574 0
2 1 28 0
8 9 368 0
8 7 138 0
7 5 30 0
2 8 313 0
6 7 153 0
7 1 272 0
4 7 182 0
9 2 369 0
9 5 80 0
5 8 877 0
2 6 689 0
7 9 219 0
8 1 334 0
4 2 453 0
2 3 86 0
0 5 239 0
7 0 245 0
5 2 314 0
3 7 324 0
4 8 164 0
8 6 897 0
5 3 371 0
2 0 280 0
0 0 0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 0
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
2 1
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 0
3 1
3 2
3 4
3 5
3 6
3 7
3 8
3 9
4 0
4 1
4 2
4 3
4 5
4 6
4 7
4 8
4 9
5 0
5 1
5 2
5 3
5 4
5 6
5 7
5 8
5 9
6 0
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 8
7 9
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 9
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
Saída para o exemplo acima
160 160
188 188
274 274
427 427
239 239
398 398
245 245
383 383
319 319
160 160
28 28
114 114
454 454
302 302
270 270
272 272
334 334
382 382
188 188
28 28
86 86
453 453
314 314
298 298
300 300
313 313
369 369
274 274
114 114
86 86
506 506
354 354
384 384
324 324
399 399
434 434
427 427
454 454
453 453
506 506
212 212
335 335
182 182
164 164
292 292
239 239
302 302
314 314
354 354
212 212
183 183
30 30
168 168
80 80
398 398
270 270
298 298
384 384
335 335
183 183
153 153
291 291
263 263
245 245
272 272
300 300
324 324
182 182
30 30
153 153
138 138
110 110
383 383
334 334
313 313
399 399
164 164
168 168
291 291
138 138
248 248
319 319
382 382
369 369
434 434
292 292
80 80
263 263
110 110
248 248

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