package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m int
	if _, err := fmt.Fscanf(reader, "%d %d\n", &n, &m); err != nil {
		return
	}

	dist := make([][]int, n)
	W := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		W[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if i == j {
				dist[i][j] = 0
				W[i][j] = 0
			} else {
				dist[i][j] = 2e18
				W[i][j] = 2e18
			}
		}
	}

	for i := 0; i < m; i++ {
		var x, y, z int
		fmt.Fscanf(reader, "%d %d %d\n", &x, &y, &z)
		x--
		y--
		if z < dist[y][x] {
			dist[y][x] = z
		}
		if z < W[y][x] {
			W[y][x] = z
		}
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] = dist[i][k] + dist[k][j]
				}
			}
		}
	}

	var q int
	fmt.Fscanf(reader, "%d\n", &q)

	for qi := 0; qi < q; qi++ {
		var k int
		fmt.Fscanf(reader, "%d\n", &k)
		a := make([]int, n)
		for i := 0; i < n; i++ {
			if i == n-1 {
				fmt.Fscanf(reader, "%d\n", &a[i])
			} else {
				fmt.Fscanf(reader, "%d", &a[i])
			}
		}

		c := make([]int, n)
		for i := 0; i < n; i++ {
			c[i] = a[i]
			for j := 0; j < n; j++ {
				if W[j][i] != 2e18 && a[j]+W[j][i] < c[i] {
					c[i] = a[j] + W[j][i]
				}
			}
		}

		res := make([]byte, n)
		for i := 0; i < n; i++ {
			possible := false
			for u := 0; u < n; u++ {
				if dist[u][i] < W[u][i] {
					cost := a[u] + dist[u][i] - c[i] + 1
					if cost < 0 {
						cost = 0
					}
					if cost <= k {
						possible = true
						break
					}
				}
			}
			if possible {
				res[i] = '1'
			} else {
				res[i] = '0'
			}
		}
		fmt.Fprintf(writer, "%s\n", string(res))
	}
}