Pink Floyd is about to give a new concert tour around the world. The band knows from previous experience that lead singer Roger Waters is constantly jittery when flying. On some routes he loses weight from excitement, while on others he eats a lot and gains weight.
It is known that the more Roger weighs, the better the band performs, so it is necessary to plan flights so that Roger's weight at each concert is the maximum possible. The band must visit the cities in the same order in which they play shows. At the same time, the group can visit intermediate cities between concerts.
Input
The first line of the input file contains three natural numbers n, m and k - the number of cities in the world, the number of flights and the number of concerts that the group should give, respectively (n≤100, m≤104, 2≤k&le ;104). Cities are numbered from 1 to n. The next m lines contain descriptions of flights, one per line. Flight number i is described by three numbers bi, ei and wi - the number of the starting and ending city of the flight and the estimated change in Roger's weight in milligrams ( 1≤bi,ei≤n, −105≤wi≤10 5). The last line contains the numbers a1, a2, ..., ak - the numbers of the cities where the concerts are held. At the beginning of the concert tour, the band is located in the city a1. It is guaranteed that the band can play all the concerts.
Output
The first line of the output file should contain the number s - the number of trips the group should make. The second line should contain s numbers - the numbers of the flights used. If there is such a sequence of routes between concerts that Roger will gain weight indefinitely, then the first line of the output file should contain the string “infinitely kind”.
|
Enter |
Output |
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
|
6
5 6 5 7 2 3
|
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
|
infinitely kind |