package main

import (
        "fmt"
	"sort"
)

/////////////////////
/////// Types ///////
/////////////////////

type Vertex struct {
	number  int
	related []*Vertex
	signals []string
}

type vertexArray []*Vertex


type DeterministicVertex struct {
	number    int
	elements  vertexArray
	related   []*DeterministicVertex
	signals   map[*DeterministicVertex][]string
}

type detVertexArray []*DeterministicVertex

func main() {
	var state_count, trans_count int
	fmt.Scan(&state_count, &trans_count)

	var vertices vertexArray
	alpha := make([]string, 0)
	vertices.declareVertex(state_count)
	alpha = vertices.initVertex(trans_count, alpha)

	final_states := make([]int, state_count)
	for i := 0; i < state_count; i++ {
		fmt.Scan(&final_states[i])
	}

	var start int
	fmt.Scan(&start)

	det(alpha, vertices, final_states, start)
}

func (vertices *vertexArray) declareVertex(state_count int) {
	*vertices = make(vertexArray, 0)

	for i := 0; i < state_count; i++ {
		vertex := Vertex{number: i, related: make(vertexArray, 0), signals: make([]string, 0)}
		*vertices = append(*vertices, &vertex)
	}
}

func (vertices vertexArray) initVertex(trans_count int, alpha []string) []string {
	for i := 0; i < trans_count; i++ {
		var temp1, temp2 int
		var label string
		fmt.Scan(&temp1, &temp2, &label)
		vertices[temp1].related = append(vertices[temp1].related, vertices[temp2])
		vertices[temp1].signals = append(vertices[temp1].signals, label)
		if !searchLabel(alpha, label) && label != "lambda" {
			alpha = append(alpha, label)
		}
	}
	return alpha
}

func searchLabel(alpha []string, label string) bool {
	for _, str := range alpha {
		if str == label {
			return true
		}
	}
	return false
}

func (dVertices *DeterministicVertex) initDVertex() {
	dVertices.signals = make(map[*DeterministicVertex][]string, 0)
	dVertices.elements = make([]*Vertex, 0)
	dVertices.related = make(detVertexArray, 0)
}

func closure(vertices vertexArray)(detVertex *DeterministicVertex) {
	detVertex = new(DeterministicVertex)
	detVertex.initDVertex()

	for _, vertex := range vertices {
		dfs(vertex, detVertex)
	}
	return detVertex
}

func dfs(vertex *Vertex, detVertex *DeterministicVertex) {
	if !detVertex.find(vertex) {
		detVertex.elements = append(detVertex.elements, vertex)
		for i, rel := range vertex.related {
			if vertex.signals[i] == "lambda" {
				dfs(rel, detVertex)
			}
		}
	}
}

func (detVertex *DeterministicVertex) find(elem *Vertex) bool {
	for _, item := range detVertex.elements {
		if item.number == elem.number {
			return true
		}
	}
	return false
}

func det(alpha []string, vertices vertexArray, final_state []int, state int) {
	start_closure := make(vertexArray, 0)
	start_closure = append(start_closure, vertices[state])
	start := closure(start_closure)			// Pointer on DeterministicVertex
	count := 0					// Numeration detVertexArray
	start.number = count
	count++
	detAutomata := make(detVertexArray, 0)		// determenistic automata
	detAutomata = append(detAutomata, start)
	isFinalS := make([]int, 0)			// Set final states

	stack := new(Stack)

	stack.Push(start)

	for stack.Len() > 0 {
		var z *DeterministicVertex
		z = stack.Pop().(*DeterministicVertex)

		for _, u := range z.elements {
			if final_state[u.number] == 1 {
				isFinalS = append(isFinalS, z.number) 	// this detVertex is final
				break
			}
		}

		for _, symbol := range alpha {
			temp := make([]*Vertex, 0)
			for _, u:= range z.elements {
				for k, g := range u.signals {
					if g == symbol {
						temp = append(temp, u.related[k])
					}
				}
			}

			new_z := closure(temp)

			if !isContainedDetVertex(detAutomata, new_z) {
				new_z.number = count
				count++
				detAutomata = append(detAutomata, new_z)
				stack.Push(new_z)
			} else {
				new_z = getNeedDetVertex(detAutomata, new_z)
			}

			z.signals[new_z] = append(z.signals[new_z], symbol)

			if !isContainedDetVertex(z.related, new_z){
				z.related = append(z.related, new_z)
			}
		}

	}

	detAutomata.printDotAutomata(isFinalS, vertices[state])
}

func isContainedDetVertex(Q detVertexArray, z *DeterministicVertex) bool {
	count := 0
	for _, item := range Q {
		count = 0
		if len(item.elements) != len(z.elements) {
			continue
		}

		for _, elem := range item.elements {
			for _, elemZ := range z.elements {
				if elem.number == elemZ.number {
					count++
				}
			}
		}

		if count == len(item.elements) {
			return true
		}
	}
	return false
}


func (detAutomata detVertexArray) printDotAutomata(final_det []int, start_vertex *Vertex) {
	fmt.Println("digraph {")
	fmt.Println("\trankdir = LR")
	fmt.Println("\tdummy [label = \"\", shape = none] ")

	for _, element := range detAutomata {
		count := 0
		fmt.Print("\t", element.number)
		fmt.Print(" [label = \"[")
		sort.Sort(element.elements)
		for _, child := range element.elements {
			if count < len(element.elements) - 1 {
				fmt.Printf("%d ", child.number)
				count++
			} else {
				fmt.Print(child.number)
			}
		}
		count = 0
		fmt.Print("]\", shape =")
		if element.isFinalS(final_det) {
			fmt.Println(" doublecircle]")
		} else {
			fmt.Println(" circle]")
		}
	}

	for _, start := range detAutomata {
		for _, elem:= range start.elements {
			if elem.number == start_vertex.number {
				fmt.Println("\tdummy ->", start.number)
			}
		}
	}


	for _, item := range detAutomata {
		for _, s := range item.related {
			count := 0
			fmt.Print("\t", item.number, " -> ", s.number)
			fmt.Print(" [label = \"")
			for _, signal := range item.signals[s] {
				if count < len(item.signals[s]) - 1 {
					count++
					fmt.Print(signal, ", ")
				} else {
					fmt.Print(signal)
				}

			}
			count = 0
			fmt.Print("\"]")
			fmt.Println()
		}
	}

	fmt.Print("}")
}

func (vertex *DeterministicVertex) isFinalS(final_det []int) bool {
	for _, final := range final_det {
		if final == vertex.number {
			return true
		}
	}
	return false
}

func getNeedDetVertex(Q detVertexArray, z *DeterministicVertex) (*DeterministicVertex) {
	count := 0
	for _, item := range Q {
		count = 0
		if len(item.elements) != len(z.elements) {
			continue
		}

		for _, elem := range item.elements {
			for _, elemZ := range z.elements {
				if elem.number == elemZ.number {
					count++
				}
			}
		}

		if count == len(item.elements) {
			return item
		}
	}
	return z
}

/////////////////////
/////// Stack ///////
/////////////////////

type Stack struct {
	top *Element
	size int
}

type Element struct {
	value interface{}
	next *Element
}

func (s *Stack) Len() int {
	return s.size
}

func (s *Stack) Push(value interface{}) {
	s.top = &Element{value, s.top}
	s.size++
}

func (s *Stack) Pop() (value interface{}) {
	if s.size > 0 {
		value, s.top = s.top.value, s.top.next
		s.size--
		return
	}
	return nil
}

/////////////////////
/////// Sort ////////
/////////////////////

func (vertices vertexArray) Len() int {
	return len(vertices)
}

func (vertices vertexArray) Swap(i, j int) {
	vertices[i], vertices[j] = vertices[j], vertices[i]
}

func (vertices vertexArray) Less(i, j int) bool {
	return vertices[i].number < vertices[j].number
}