program travel (input,output);

const

   INFINITY = 1000.0;
   MAXCITIES = 100;
   NOPATH = -1;

var

   graph: array[1..MAXCITIES,1..MAXCITIES] of real;
   delay: array[1..MAXCITIES] of real;
   preds: array[1..MAXCITIES] of integer; (* predecessor *)
   numCities: integer;
   cost: real;

procedure initGraph;
var
  i,j: integer;
begin
   for i := 1 to MAXCITIES do begin
    for j := 1 to MAXCITIES do begin
       if i=j
          then graph[i,i] := 0.0
       else 
	  graph[i,j] := INFINITY;
    end;
  end;
end;

procedure readCities(var numCities: integer);
var
  c: integer;
begin
   (* write('how many cities> '); *)
   readln(numCities);
   for c := 1 to numCities do begin
      read(delay[c]);
   end;
   readln;
end;

procedure readLinks;
var
  x,y: integer;
  d: real;
begin
   (* write('please enter the links between cities in this format:'); *)
   (* writeln(' city#1 city#2 time-en-route'); *)
   readln(x,y,d); 
   while (x > 0) do begin
	graph[x,y] := d;
	graph[y,x] := d;
	readln(x,y,d);
   end
end;

procedure addDelays(numCities: integer);
var
  c,j: integer;
  d: real;
begin
   for c := 1 to numCities do begin
      if (c = 1) or (c = numCities) then
        d := delay[c]
      else
        d := delay[c] / 2.0;
      for j := 1 to numCities do begin
 	if graph[c,j] < INFINITY then begin
		graph[c,j] := graph[c,j] + d;
		graph[j,c] := graph[j,c] + d;
	end
      end
   end
end;

function Dijkstra(numCities: integer) : real ;
var
   S: array[1..MAXCITIES] of boolean; (* already searched *)
   L: array[1..MAXCITIES] of real;    (* cost of path *)
   i, pathLen : integer;
   minNode: integer; 
   minCost, segment: real; 
begin
   S[1] := true; 
   for i:=2 to numCities do begin
      if (graph[1,i] < INFINITY) then
         preds[i] := 1
      else
         preds[i] := 0; 
      S[i] := false; 
      L[i] := graph[1,i];
   end;

   for pathLen := 2 to numCities do begin
      minNode := 0;
      minCost := INFINITY;
      for i := 2 to numCities do begin
         if (S[i] = false) then
	    if (L[i] < minCost) then begin
	       minCost := L[i];
	       minNode := i;
            end;
      end;

      if (minNode = 0) then begin
         Dijkstra := L[numCities];
         exit;
      end;

      S[minNode] := true;
      for i := 2 to numCities do begin
         if (S[i] = false) then begin   
            segment := L[minNode] + graph[minNode,i];
	    if L[i] > segment then begin
	       L[i] := segment;
               preds[i] := minNode; 
            end;
	 end;
      end;
   end;

   Dijkstra := L[numCities];
end;

procedure printPath(numCities: integer ; cost : real);
var
   i, loc : integer;
   path: array[1..MAXCITIES] of integer; 
begin
   i := 1;
   loc := numCities;
   path[i] := loc;
   while (preds[loc] > 1) do begin
       loc := preds[loc];
       i := i+1;
       path[i] := loc;
   end;

   if (preds[loc] = 0) then begin
       writeln('No path found');
   end else begin
       loc := i + 1;
       path[loc] := 1;
       writeln('Shortest time: ', cost:12:0);
       write('Shortest path: ');
       for i := loc downto 1 do begin
           write(path[i]:4);
       end;
       writeln;
   end;
end;

begin
   initGraph;
   readCities(numCities);
   readLinks;
   addDelays(numCities);
   cost := Dijkstra(numCities);
   printPath(numCities, cost);
end.