1. 

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11635 Hotel Booking
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2682
*
* @author Martin Lambeck
* @version 1.0, 07/27/2010
*
* Method : dijkstra
* Status : Accepted
* Runtime: 1.708
*/

import java.util.ArrayList;
import java.util.PriorityQueue;

class Main
{
static BufferedIntReader r = new BufferedIntReader(); //reads int from stdin
static ArrayList<City> cities = new ArrayList<City>(10000); //all cities
static PriorityQueue<City> unvisited = new PriorityQueue<City>(500); //priority q sorted after stops,costs

static int cityCount;

public static void main (String...args) throws Exception
{
//double start = System.currentTimeMillis();

for (int i = 0; i < 10000; i++)
cities.add(new City(i+1));

while(testcase());

//System.out.println((System.currentTimeMillis() - start) / 1000.0 + " sek.");

}

public static boolean testcase() throws Exception
{
int hotelCount;
int roadCount;

cityCount = r.nextInt();

if (cityCount <= 0)
return false;


//attention!
//the cities array may contain more cities than used in this testcase
//so dont use a foreach loop over the cities!

for (int i = 0; i < cityCount; i++)
cities.get(i).reset();


hotelCount = r.nextInt();

for (int i = 0; i < hotelCount; i++)
cities.get(r.nextInt() - 1).hotel = true; //this city has a hotel



roadCount = r.nextInt();

for (int i = 0; i < roadCount; i++)
{
City c1 = cities.get(r.nextInt() - 1);
City c2 = cities.get(r.nextInt() - 1);
int time = r.nextInt();

c1.roads.add(new Edge(time, c2));
c2.roads.add(new Edge(time, c1));
}


System.out.println(work());

return true;
}

static int work()
{
City destination = cities.get(cityCount-1);

//algorithm will only work with this
cities.get(0).hotel = true;
cities.get(cityCount-1).hotel = true;
cities.get(0).stops = -1; //set as start

int day = 0; // current day

while (dijk(day))
{
if (destination.stops < Integer.MAX_VALUE) //reached destination
return day;

day++;
}

return -1;
}

/*
* dijkstra algorithm.
* calculates the reachable cities at this day!
* starts from hotels reached the day before
*
* return true, if new hotels were reached at this day
* false otherwise (=> impossible to reach destination)
*/
static boolean dijk(int day)
{
Edge rd;
City c;
boolean passedHotel = false; //whether a new hotel was reached

unvisited.clear();

//initialize
for (int i = 0; i < cityCount; i++)
{
c = cities.get(i);

if (c.hotel && c.stops == day-1) // the hotel was discovered the day before
{
c.costs = 0;
unvisited.add(c); //this is a starting point for today

} else if (c.hotel && c.stops <= day-1) //any other hotel we have been before
{
c.costs = 0; //prevents hotel from being updated

} else //any other city
{
c.costs = Integer.MAX_VALUE; //set city to not be reached yet

//this part could really be improved....
}
}


while (unvisited.size() > 0)
{
City cur = unvisited.poll(); //get city with lowest cost


for (int i = 0; i < cur.roads.size(); i++) //iterate thru connected cities
{
rd = cur.roads.get(i);

int costs = cur.costs + rd.time; //new costs

if (costs <= 600 && costs < rd.to.costs) //if below the daily limit, and lower than before
{
rd.to.costs = costs; //update

if (rd.to.hotel) //we reached a hotel...
{
passedHotel = true; //which will serve as a starting point for tomorrow
rd.to.stops = day; //set the day we reached this hotel
}

unvisited.add(rd.to); //maybe we can go further from this city
}
}
}

return passedHotel;
}
}

class City implements Comparable<City>
{
int id; //number of the city
boolean hotel = false;
ArrayList<Edge> roads = new ArrayList<Edge>(200);
int costs = Integer.MAX_VALUE;
int stops = Integer.MAX_VALUE;

public City (int id)
{
this.id = id;
}

public void reset()
{
roads.clear();
hotel = false;
stops = Integer.MAX_VALUE;
costs = Integer.MAX_VALUE;
}

public int compareTo(City other)
{
//if (stops == other.stops)
//{
if (costs > other.costs)
return 1;

if (costs < other.costs)
return -1;

return 0;

//return (costs < other.costs ? -1 : 1);
//}

//return (stops < other.stops ? -1 : 1);
}
}


class Edge
{
int time;
City to;

public Edge(int time, City to)
{
this.time = time;
this.to = to;
}
}

//reads int from stdin
class BufferedIntReader
{
byte[] buf = new byte[1024*32];
int pos = 0;
int len = 0;

public int nextInt() throws Exception
{
int num = 0;
int chr;
boolean found = false;

while (true)
{
if (pos == len)
{
pos = 0;
len = System.in.read(buf);
}

if (len == -1)
{
found = true;
chr = -1;

} else
{
chr = buf[pos];
pos++;
}

if (chr >= '0' && chr <= '9')
{
num = num*10 + (chr - '0');
found = true;

} else
{
if (found)
return num;
}
}
}
}