Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DESAFIO - Desafio das Moedas Prateadas

O Desafio das Moedas Prateadas é um esporte individual popular no reino de Diddykongolândia. O campo e as regras do jogo são descritos a seguir.

O campo do jogo consiste em locais e trechos. Há N locais no campo. Um desses locais é o local de largada, no qual o jogador inicia o jogo.

M trechos no campo. Cada trecho é uma via unidirecional que liga um local do campo a outro local distinto. Os trechos são os únicos meios pelos quais o jogador pode se mover entre os locais do campo. Os trechos do campo são dados de tal forma que:

  • é possível ir do local de largada a qualquer outro local usando os trechos;
  • é possível ir de qualquer local do campo ao local de largada usando os trechos;
  • é impossível sair de um local l e voltar para o mesmo local l sem passar pelo local de largada.

Há também K moedas prateadas no jogo. Cada moeda está em um local distinto do campo. Se o jogador chegar a um local que contém uma moeda, o jogador pode coletá-la. Não há moeda no local de largada.

O jogador começa o jogo no local de largada. Uma volta é completada pelo jogador quando ele retorna ao local de largada após passar por outro(s) local(is).

O jogador deve completar exatamente três voltas. Se o jogador conseguir coletar todas as moedas de prata antes de completar a última volta, ele vence. Caso contrário, ele perde.

Após analizar o campo de jogo, você descobriu quanto tempo leva para atravessar cada trecho. Agora, você deve descobrir se é possível vencer no campo dado e, em caso positivo, qual o tempo mínimo que você deve levar para vencer. Considere instantâneo o tempo para coletar uma moeda e para atravessar um local (sair de um trecho e entrar em outro adjacente).

Entrada

A entrada inicia com uma linha contendo três inteiros N, M e K (2 ≤ N ≤ 1000, 2 ≤ M ≤ (N2 + N - 2)/2, 1 ≤ K ≤ min{12, N-1}), indicando o número de locais, de trechos e de moedas no campo. Os locais são numerados de 1 a N. O local 1 é o local de largada.

As próximas M linhas descrevem os trechos. Cada trecho é descrito por três inteiros la, lb e t (1 ≤ la, lbN, lalb, 1 ≤ t ≤ 104), indicando que há um trecho que leva do local la para o local lb que é atravessado em t segundos.

A última linha contém K inteiros distintos ki (2 ≤ kiN para 1 ≤ i ≤ K) indicando os locais das moedas prateadas.

Saída

Se não é possível vencer o jogo, imprima uma linha contendo impossivel. Caso contrário, imprima uma linha contendo o menor tempo possível, em segundos, para vencer o jogo.

Examplos

Entrada:
4 6 3
1 2 1
1 3 1
1 4 1
2 1 1
3 1 1
4 1 1
2 3 4 Saída: 6

Entrada:
5 7 2
1 2 1
1 3 2
2 3 3
3 4 7
3 5 3
4 5 2
5 1 4
2 4 Saída: 35

Entrada:
5 8 4
1 2 3
1 3 2
1 4 10
1 5 7
2 1 5
3 1 3
4 1 1
5 1 12
4 5 3 2 Saída: impossivel


Adicionado por:Ricardo Oliveira [UFPR]
Data:2014-08-10
Tempo limite:2s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva UFPR 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.