根据 LP对偶（我不会的东西）有这么个结论：

最大费用循环流等价于：

$$\min \sum_{(u, v) \in E} c(u, v) \max \left(w(u, v)+h_{u}-h_{v}, 0\right)$$

其中 $h_u$ 是给每个点任意定的一个权值，$c(u,v)$ 为一条边的容量，$w(u,v)$ 为一条边的费用。可以带入最大流和最小割验证。

对于这个题，如果二分答案为 $\lambda$ ，我们相当于是要最小化

$$\sum x_{u,v}$$

满足

$$d_u + x_{u,v} + w_{u,v} \ge d_v\\d_1 + \lambda \ge d_n$$

考虑怎么凑成前面的形式，对于第二个不等式，我们直接给 $d_1 + \lambda - d_n$ 乘个系数 $\infty$ 表示必须满足，前面那个写成 $x_{u,v} \ge d_v - d_u - w_{u,v}$ ，考虑既然要最小化且非负，相当于是 $\max(d_v - d_u - w_{u,v} , 0)$ 于是就是：

$$\min \left(\max \left(\lambda+d_{1}-d_{n}, 0\right) \infty+\sum_{(u, v) \in E} \max \left(d_{v}-d_{u}-w(u, v), 0\right)\right)$$

它相当于是一个从 $1$ 到 $n$ 连了一条容量无穷，费用 $L$ 的边，然后 $v$ 向 $u$ 有一条容量为 $1$ 费用为 $-w(u,v)$ 的边做最大循环费用流。

发现只有 $\lambda$ 可以增加费用，所以肯定会，所以相当于是去掉那条边后从 $n$ 到 $1$ 需要一条最大费用最大流。可以稍微转化一下把边权全部取反变成从 $1$ 到 $n$ 的最小费用最大流。

这样是可以 check 了。注意到我们本质上就是要最大化这里的 $\lambda$ ，貌似可以直接做的。

我们考虑从 $1$ 到 $n$ 用单路增广来做最小费用最大流，那么对于一条最短路，明显它要么不取，要么全部取走，所以可以直接枚举单路增广的路径，然后和当前的答案比较一下，取较小值即可。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"

using namespace std;
#define MAXN 200006
//#define int long long
#define rep( i , a , b ) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per( i , a , b ) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all( x ) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353

int n , s , t;
int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , wto[MAXN << 1] , cto[MAXN << 1] , ecn = -1;

void ade( int u , int v , int w , int c ) {
//	cout << u << ' ' << v << ' ' << w << ' ' << c << endl;
	to[++ecn] = v , nex[ecn] = head[u] , wto[ecn] = w , head[u] = ecn , cto[ecn] = c;
	to[++ecn] = u , nex[ecn] = head[v] , wto[ecn] = 0 , head[v] = ecn , cto[ecn] = -c;
}

queue<int> Q;
int dis[MAXN] , pre[MAXN] , vis[MAXN];
const int inf = 1e9;

bool spfa( int s ) {
	mem( vis );
	Q.push( s );
	memset( dis , 0x3f , sizeof dis );
	memset( pre , -1 , sizeof pre );
	dis[s] = 0 , vis[s] = 1;
	while( !Q.empty( ) ) {
		int u = Q.front( );
		Q.pop( );
		vis[u] = 0;
		for( int i = head[u] ; ~i ; i = nex[i] )
			if( wto[i] && dis[to[i]] > dis[u] + cto[i] ) {
				int v = to[i];
				dis[v] = dis[u] + cto[i];
				pre[v] = i;
				if( !vis[v] ) Q.push( v ) , vis[v] = 1;
			}
	}
	return pre[t] != -1;
}

vector<pii> fc;
int flow , co;
void doit( ) {
	int T = t , fl = 0x3f3f3f3f;
	while( ~pre[T] ) fl = min( fl , wto[pre[T]] ) , T = to[pre[T] ^ 1];
	flow += fl , co += fl * dis[t];
	fc.eb( mp( flow , co ) );
	T = t;
	while( ~pre[T] ) wto[pre[T]] -= fl , wto[pre[T] ^ 1] += fl , T = to[pre[T] ^ 1];
}

void mcmf( ) {
	flow = co = 0;
	while( spfa( s ) )
		doit( );
}

void solve( ) {
	memset( head , -1 , sizeof head );
	int n , m; cin >> n >> m;
	::n = n; s = 1 , t = n;
	rep( i , 1 , m ) {
		static int u , v , w;
		scanf("%d%d%d",&u,&v,&w) , ade( u , v , 1 , w );
	}
	mcmf( );
	int q;cin >> q;
	double re;
	while( q-- ) {
		static int x;
		re = 1e9;
		scanf("%d",&x);
		for( auto& t : fc )
			re = min( re , 1. * ( t.se + x ) / t.fi );
		printf("%.8lf\n",re);
	}
}

signed main( ) {
//	freopen("input","r",stdin);
//	freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve( );
}