import java.util.*;


class f_joe
{
	public static void main(String Args[])
	{
		new f_joe();
	}
	int TankSize;
	TreeMap<Integer, City> Cities;
	int Start;
	int Goal;

	public f_joe()
	{
		int Cz;
		int R;
		Scanner in=new Scanner(System.in);
		Cities=new TreeMap<Integer,City>();
		Cz=in.nextInt();
		R=in.nextInt();
		for(int i=0; i<Cz; i++)
		{
			City c=new City();
			c.FuelPrice = in.nextInt();
			Cities.put(i,c);
		}
		for(int i=0; i<R; i++)
		{
			int s;
			int e;
			int d;
			s=in.nextInt(); e=in.nextInt(); d=in.nextInt();
			Cities.get(s).Next.put(e,d);
			Cities.get(e).Next.put(s,d);
		}

		int Q;
		Q=in.nextInt();
		for(int q=0; q<Q; q++)
		{
			TankSize=in.nextInt();
			Start=in.nextInt();
			Goal=in.nextInt();
			for(int i=0; i<Cz; i++)
			{
				Cities.get(i).reset();
			}
			int cost=search();
			if (cost >= 1000000000)
			{
				System.out.println("impossible");
			}
			else
				System.out.println(cost);
		}



		

	}

	class CheckData
	{
		int CityNum;
		City C;
		int Fuel;

		public CheckData(int cn, City c, int f)
		{
			CityNum=cn;
			C=c;
			Fuel=f;
		}
		
	}

	int search()
	{
		Random Rnd=new Random();
		TreeMap<Double,CheckData> check; //List of cities to check

		check=new TreeMap<Double,CheckData>();
		check.put(0.0,new CheckData(Start,Cities.get(Start),0));

		Cities.get(Start).Costs.set(0,0);

		while(check.size()>0)
		{
			double d=check.firstKey();
			CheckData CD=check.get(d);
			City C=CD.C;
			int i=CD.Fuel;
			check.remove(d);
			if (CD.CityNum==Goal)
			{
				return C.Costs.get(i);
			}

				if (C.Costs.get(i) < 1000000000)
				{
					int cost=C.Costs.get(i);
					int maxfill=TankSize-i;
					for(int j=0; j<=maxfill; j++)
					{
						int cost2=cost + j * C.FuelPrice;
						for(Map.Entry<Integer,Integer> me : C.Next.entrySet())
						{
							int next=me.getKey();
							int dist=me.getValue();
							int f2=i + j - dist;
							if (f2 >=0)
							{
								City C2=Cities.get(next);
								if (cost2 < C2.Costs.get(f2))
								{
									C2.Costs.set(f2,cost2);
									check.put(Rnd.nextDouble() + cost2, new CheckData(next,C2,f2));
								}
							}

						}
					}
				}
		}

		return Cities.get(Goal).Costs.get(0);

	}


	class City
	{
		TreeMap<Integer, Integer> Next; //city -> dist

		ArrayList<Integer> Costs; //gas -> cost
		int FuelPrice;

		public City()
		{
			Next=new TreeMap<Integer,Integer>();
		}
		public void reset()
		{

			Costs=new ArrayList<Integer>();
			for(int i=0; i<=TankSize; i++)
			{
				Costs.add(1000000000);
			}
		}

	}
}