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;
template <typename flow_t, typename cost_t>
struct min_cost_flow {
  const cost_t COST_INF = numeric_limits<cost_t>::max() / 2;
  struct edge {
    int node, rev;
    flow_t capacity;
    cost_t cost;
    edge() {}
    edge(int _node, int _rev, flow_t _capacity, cost_t _cost)
        : node(_node), rev(_rev), capacity(_capacity), cost(_cost) {}
  };
  int V = -1, E = 0;
  vector<vector<edge>> adj;
  vector<cost_t> dist;
  vector<int> prev;
  vector<edge *> prev_edge;
  bool too_many_bellman_ford_iterations = false;
  min_cost_flow(int vertices = -1) {
    if (vertices >= 0) init(vertices);
  }
  void init(int vertices) {
    V = vertices;
    E = 0;
    adj.assign(V, {});
    dist.resize(V);
    prev.resize(V);
    prev_edge.resize(V);
    too_many_bellman_ford_iterations = false;
  }
  void add_directional_edge(int u, int v, flow_t capacity, cost_t cost) {
    assert(0 <= u && u < V && 0 <= v && v < V);
    edge uv_edge(v, adj[v].size() + (u == v ? 1 : 0), capacity, cost);
    edge vu_edge(u, adj[u].size(), 0, -cost);
    adj[u].push_back(uv_edge);
    adj[v].push_back(vu_edge);
    E++;
  }
  edge &reverse_edge(const edge &e) { return adj[e.node][e.rev]; }
  bool bellman_ford(int source, int sink) {
    for (int i = 0; i < V; i++) {
      dist[i] = COST_INF;
      prev[i] = -1;
      prev_edge[i] = nullptr;
    }
    long long work = 0;
    vector<int> last_seen(V, -1);
    vector<int> nodes = {source}, next_nodes;
    dist[source] = 0;
    for (int iteration = 0; iteration < V; iteration++) {
      next_nodes.clear();
      for (int node : nodes) {
        for (edge &e : adj[node])
          if (e.capacity > 0 && dist[node] + e.cost < dist[e.node]) {
            dist[e.node] = dist[node] + e.cost;
            prev[e.node] = node;
            prev_edge[e.node] = &e;
            if (last_seen[e.node] != iteration) {
              last_seen[e.node] = iteration;
              next_nodes.push_back(e.node);
            }
          }
        work += adj[node].size();
      }
      swap(nodes, next_nodes);
    }
    if (work > 1.75 * E * (32 - __builtin_clz(V)) + 100)
      too_many_bellman_ford_iterations = true;
    return prev[sink] != -1;
  }
  struct dijkstra_state {
    cost_t dist;
    int node;
    dijkstra_state() {}
    dijkstra_state(cost_t _dist, int _node) : dist(_dist), node(_node) {}
    bool operator<(const dijkstra_state &other) const {
      return dist > other.dist;
    }
  };
  void dijkstra_check(int node, cost_t potential_dist, int previous,
                      edge *previous_edge, priority_queue<dijkstra_state> &pq) {
    if (potential_dist < dist[node]) {
      dist[node] = potential_dist;
      prev[node] = previous;
      prev_edge[node] = previous_edge;
      pq.emplace(dist[node], node);
    }
  }
  bool dijkstra(int source, int sink) {
    dist.assign(V, COST_INF);
    prev.assign(V, -1);
    prev_edge.assign(V, nullptr);
    priority_queue<dijkstra_state> pq;
    dijkstra_check(source, 0, -1, nullptr, pq);
    while (!pq.empty()) {
      dijkstra_state top = pq.top();
      pq.pop();
      if (top.dist > dist[top.node]) continue;
      for (edge &e : adj[top.node])
        if (e.capacity > 0)
          dijkstra_check(e.node, top.dist + e.cost, top.node, &e, pq);
    }
    return prev[sink] != -1;
  }
  void reduce_cost() {
    for (int i = 0; i < V; i++)
      for (edge &e : adj[i])
        if (dist[i] < COST_INF && dist[e.node] < COST_INF)
          e.cost += dist[i] - dist[e.node];
  }
  vector<pair<flow_t, cost_t>> options;
  pair<flow_t, cost_t> solve_min_cost_flow(
      int source, int sink, flow_t flow_goal = numeric_limits<flow_t>::max()) {
    assert(V >= 0);
    flow_t total_flow = 0;
    cost_t total_cost = 0;
    while (total_flow < flow_goal && bellman_ford(source, sink)) {
      if (too_many_bellman_ford_iterations) break;
      flow_t path_cap = flow_goal - total_flow;
      cost_t cost_sum = 0;
      for (int node = sink; prev[node] != -1; node = prev[node])
        path_cap = min(path_cap, prev_edge[node]->capacity);
      for (int node = sink; prev[node] != -1; node = prev[node]) {
        edge *e = prev_edge[node];
        e->capacity -= path_cap;
        reverse_edge(*e).capacity += path_cap;
        cost_sum += e->cost;
      }
      total_flow += path_cap;
      total_cost += cost_sum * path_cap;
      options.emplace_back(total_flow, total_cost);
    }
    if (too_many_bellman_ford_iterations) {
      cost_t reduce_sum = 0;
      do {
        reduce_cost();
        reduce_sum += dist[sink];
        flow_t path_cap = flow_goal - total_flow;
        for (int node = sink; prev[node] != -1; node = prev[node])
          path_cap = min(path_cap, prev_edge[node]->capacity);
        for (int node = sink; prev[node] != -1; node = prev[node]) {
          edge *e = prev_edge[node];
          assert(e->cost == 0);
          e->capacity -= path_cap;
          reverse_edge(*e).capacity += path_cap;
        }
        total_flow += path_cap;
        total_cost += reduce_sum * path_cap;
        options.emplace_back(total_flow, total_cost);
      } while (total_flow < flow_goal && dijkstra(source, sink));
    }
    return make_pair(total_flow, total_cost);
  }
};
int main() {
  int N, M;
  scanf("%d %d", &N, &M);
  min_cost_flow<int, long long> graph(N);
  for (int i = 0; i < M; i++) {
    int u, v, weight;
    scanf("%d %d %d", &u, &v, &weight);
    u--;
    v--;
    graph.add_directional_edge(u, v, 1, weight);
  }
  graph.solve_min_cost_flow(0, N - 1);
  int Q;
  scanf("%d", &Q);
  for (int q = 0; q < Q; q++) {
    int x;
    scanf("%d", &x);
    double answer = 1e100;
    for (auto &option : graph.options)
      answer = min(answer, (double)(option.second + x) / option.first);
    printf("%.9lg\n", answer);
  }
}