Problem: Farmer John is obsessed with making Bessie exercise more!

Bessie is out grazing on the farm, which consists of n fields connected by m directed roads. Each road takes some time w_i to cross. She is currently at field 1 and will return to her home at field n at the end of the day.

Farmer John has plans to increase the time it takes to cross certain roads. He can increase the time it takes to cross each road by a nonnegative amount, but the total increase cannot exceed x_i for the i-th plan. 

Determine the maximum he can make the shortest path from 1 to n for each of the q independent plans.

Input

The first line contains integers n and m (2 ≤ n ≤ 50, 1 ≤ m ≤ n ⋅ (n-1)) — the number of fields and number of roads, respectively.

Each of the following m lines contains 3 integers, u_i, v_i, and w_i (1 ≤ u_i, v_i ≤ n, 1 ≤ w_i ≤ 10^6), meaning there is an road from field u_i to field v_i that takes w_i time to cross.

It is guaranteed that there exists a way to get to field n from field 1. It is guaranteed that the graph does not contain self-loops or parallel edges. It is possible to have a road from u to v and a road from v to u.

The next line contains a single integer q (1 ≤ q ≤ 10^5), the number of plans.

Each of the following q lines contains a single integer x_i, the query (0 ≤ x_i ≤ 10^5).

Output

For each query, output the maximum Farmer John can make the shortest path if the total increase does not exceed x_i.

Your answer is considered correct if its absolute or relative error does not exceed 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Example

Input


3 3
1 2 2
2 3 2
1 3 3
5
0
1
2
3
4


Output


3.0000000000
4.0000000000
4.5000000000
5.0000000000
5.5000000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int pct(int x) { return __builtin_popcount(x); }
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = {a, b};
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
T poll(pqg<T>& x) {
  T y = x.top();
  x.pop();
  return y;
}
template <int SZ>
struct MCMF {
  struct Edge {
    int to, rev;
    long long flow, cap;
    long long cost;
  };
  vector<Edge> adj[SZ];
  void ae(int u, int v, long long cap, long long cost) {
    assert(cap >= 0);
    Edge a{v, (int)adj[v].size(), 0, cap, cost},
        b{u, (int)adj[u].size(), 0, 0, -cost};
    adj[u].push_back(a), adj[v].push_back(b);
  }
  int N, second, t;
  pair<int, int> pre[SZ];
  pair<long long, long long> cost[SZ];
  long long curCost;
  long long totFlow;
  bool spfa() {
    for (int i = (0); i < (N); ++i)
      cost[i] = {numeric_limits<long long>::max(), 0};
    cost[second] = {0, numeric_limits<long long>::max()};
    pqg<pair<long long, int>> todo;
    todo.push({0, second});
    while ((int)todo.size()) {
      auto x = poll(todo);
      if (x.first > cost[x.second].first) continue;
      for (auto& a : adj[x.second])
        if (a.flow < a.cap && ckmin(cost[a.to].first, x.first + a.cost)) {
          pre[a.to] = {x.second, a.rev};
          cost[a.to].second = min(a.cap - a.flow, cost[x.second].second);
          todo.push({cost[a.to].first, a.to});
        }
    }
    return cost[t].second;
  }
  vector<int> totCost;
  void backtrack() {
    long long df = cost[t].second;
    totFlow += df;
    curCost += cost[t].first;
    totCost.push_back(curCost);
    for (int x = t; x != second; x = pre[x].first) {
      adj[x][pre[x].second].flow -= df;
      adj[pre[x].first][adj[x][pre[x].second].rev].flow += df;
    }
    for (int i = (0); i < (N); ++i)
      for (auto& p : adj[i]) p.cost += cost[i].first - cost[p.to].first;
  }
  void calc(int _N, int _s, int _t) {
    N = _N;
    second = _s, t = _t;
    totFlow = curCost = 0;
    while (spfa()) backtrack();
  }
};
MCMF<51> M;
int n, m;
int main() {
  setIO();
  re(n, m);
  for (int i = (0); i < (m); ++i) {
    int u, v, w;
    re(u, v, w);
    M.ae(u, v, 1, w);
  }
  M.calc(n + 1, 1, n);
  int Q;
  re(Q);
  cout << fixed << setprecision(9);
  for (int i = (0); i < (Q); ++i) {
    int X;
    re(X);
    long long ans = 0;
    for (int i = (0); i < ((int)M.totCost.size() + 1); ++i) {
      if (i) {
        long long up = (i == (int)M.totCost.size() ? MOD : M.totCost[i]);
        long long ANS = ans + (up - M.totCost[i - 1]) * i;
        if (ANS >= X) {
          ps(M.totCost[i - 1] + (double)(X - ans) / i);
          break;
        }
        ans = ANS;
      }
    }
  }
}