Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4078
Accel World

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

Chiaki was trapped in a strange place which can be regarded as a connected undirected graph with $n$ vertices (numbered from $1$ to $n$) and $m$ weighted edges (numbered from $1$ to $m$). In the beginning, Chiaki is at vertex $1$ with speed $v$ equals to $1$ unit per second and would like to go to the vertex $n$.

There are some special vertices in the graph, called \textit{acceleration vertex}. Once Chiaki reached an acceleration vertex, her speed will be doubled: from $v$ to $2v$. The same acceleration vertex can be used multiple times to achieve multiple acceleration, but it only works under this limitation: the last acceleration vertex Chiaki visited should not equal to the current acceleration vertex Chiaki reached.

For example, vertex $2$ and $3$ are acceleration vertices while $1$, $4$ and $5$ are not. If Chiaki chooses the path $1 \to 2 \to 3 \to 2 \to 5$, Chiaki's speed would be accelerated for three times ($8$ unit per second in the end). But if the path is $1 \to 2 \to 4 \to 2 \to 4 \to 2 \to 5$, Chiaki would have only one acceleration.

Chiaki would like to know the minimum time needed to reach the vertex $n$.


There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 100$, $1 \le m \le 8000$, $0 \le k \le n$) -- the number of vertices, the number of edges and the number of special vertices.

Each of the following $m$ lines contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 1000$) denoting an edge with $w_i$ unit length connecting $u_i$ and $v_i$.

The next line contains $k$ integers $p_1,p_2,\dots,p_k$ ($2 \le p_i \le n - 1$) denoting the index of each \textit{acceleration vertex}.

It's guaranteed that the sum of $n$ over all test cases will not exceed $1000$ and the sum of $m$ over all test cases will not exceed $80000$.


For each test case, output a real number $t$ denoting the minimum time to reach the vertex $n$ and an integer $s$ denoting the maximum times of acceleration Chiaki can achieve among all optimal solutions.

Your answer for $t$ will be considered correct if and only if the absolute error or relative error of your answer is less than $10^{-6}$. And by the way, if $s$ is greater than $32767$, output "Burst!" (without the quotes) instead.

Sample Input

2 1 2
1 2 1
1 2
5 4 2
1 2 1
2 3 1
3 4 1
4 5 1
2 3
6 7 2
1 2 2
2 4 2
4 6 2
1 3 2
3 4 2
4 5 4
5 6 4
3 4

Sample Output

0.5000000000 2
2.0000000000 Burst!
3.5000000000 2

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status