package main

import (
        "fmt"
    "strconv"
)
type Transition struct {
    nextState int
    label     string
}

type State struct {
    pos         int
    transitions []Transition
    isFinal     bool
}


type Machine struct {
    states []State
    X      []string
    F      []int
    statesAmount int
}


type HashTable struct {
    place   int
    isTaken bool
}


func (m *Machine) addState(s string){
    if s=="lambda"{
        return
    }
    for _,S:=range m.X{
        if s==S{
            return
        }
    }
    m.X=append(m.X,s)
}

func (v *State) addEdge(e Transition){
    v.transitions =append(v.transitions,e)
}

var lambda string

func main() {
    var n,m int
    lambda="lambda"
    fmt.Scan(&n,&m)
    machine := Machine{}
    machine.states =make([]State,n)
    machine.X=make([]string,0)
    machine.F=make([]int,n)
    for i:=0;i<n;i++{
        machine.states[i].pos =i;
        machine.states[i].transitions =make([]Transition,0)
    }
    machine.statesAmount=m
    from,to,s:=0,0,""
    for i:=0;i<m;i++ {
        fmt.Scan(&from, &to, &s)
        machine.states[from].addEdge(Transition{to, s})
        machine.addState(s)
    }
    for i:=0;i<n;i++{
        fmt.Scan(&machine.F[i])
    }
    var k int
    fmt.Scan(&k)
    fmt.Println(Det(&machine, machine.states[k]))
}


type Set struct {
    set []State
}

func (set *Set) init(){
    set.set=make([]State,0)
}
func (set *Set) add(q State)bool{
    for _,elem:=range set.set{
        if elem.pos ==q.pos {
            return false
        }
    }
    set.set=append(set.set,q)
    return true
}

func Closure(z []State, machine Machine) []State {
    set:=Set{}
    set.init()
    for i:=0;i<len(z);i++{
        dfs(z[i], machine,&set)
    }
    return set.set
}

func dfs(q State,  machine Machine,set *Set,) {
    if set.add(q) {
        for _, transition := range machine.states[q.pos].transitions {
            if transition.label == lambda {
                dfs(machine.states[transition.nextState], machine,set)
            }
        }
    }
}

var hashTable []HashTable

func getValue(nodes []State,size int) int{
    sum, multi, sqr :=0,1,0
    for _, node :=range nodes {
        multi *= node.pos
        sum += node.pos
        sqr += node.pos * node.pos
    }
    sum = sum + multi + sqr
    res:=sum%size
    return res
}


func evalSize(machine *Machine){
    if machine.statesAmount>5{
        size=100
    }else {
        size=10
    }
}

var size int
func Det(machine *Machine,q State) string{
    evalSize(machine)
    Q,q0, container,F, labels := createCapabilities(q, machine)
    hashTable=make([]HashTable,size)
    container = append(container,q0)
    hashTable[getValue(q0,size)]= HashTable{0,true}
    return DOT(determine(Q, container, machine,F, 1,labels))
}

func determine(Q [][]State, container [][]State, machine *Machine,F [][]State, index int,labels [][]string) ([][]State,[][]State,[][]string){
    for ;len(container)>0;{
        z:= container[0]
        for _, state :=range z{
            if machine.F[state.pos]!=0{
                F=append(F,z)
                break
            }
        }
        for _,a:=range machine.X{
            states:=connectSets(z,machine,a)
            if !hashTable[getValue(states,size)].isTaken {
                Q = append(Q, states)
                container = append(container, states)
                hashTable[getValue(states,size)] = HashTable{index,true}
                index++
            }
            labels[hashTable[getValue(z,size)].place][hashTable[getValue(states,size)].place]+=a
            labels[hashTable[getValue(z,size)].place][hashTable[getValue(states,size)].place]+=", "
        }
        container1 := container[1:]
        container=container1
    }
    return Q,F,labels
}


func connectSets(z []State,machine *Machine, lbl string) []State{
    states :=make([]State,0)
    for _, state :=range z{
        for _, transition :=range state.transitions {
            if transition.label== lbl {
                states =append(states, machine.states[transition.nextState])
            }
        }
    }
    states = Closure(states,*machine)
    return states
}

func createCapabilities(q State, machine *Machine)([][]State,[]State,[][]State,[][]State,[][]string){
    q0:=make([]State,0)
    q0=append(q0,q)
    q0= Closure(q0,*machine)
    Q:=make([][]State,0)
    Q=append(Q,q0)
    stks :=make([][]State,0)
    F:=make([][]State,0)
    delta_matrix :=make([][]string,size)
    for i:=0;i<len(delta_matrix);i++{
        delta_matrix[i]=make([]string, size)
    }
    return Q,q0,stks,F,delta_matrix
}
func DOT(states [][]State, Final [][]State, labels [][]string)string{
    final:=make([]bool,len(states))
    for i:=0;i<len(Final);i++ {
        final[hashTable[getValue(Final[i],size)].place]=true
    }
    for _,z:=range states {
        quickSort(z)
    }
    output:= composer(states,final, labels)
    return output
}

func composer(states [][]State, final []bool, labels [][]string)string{
    output :="digraph {\nrankdir = LR\ndummy [label = \"\", shape = none]"
    output +="\n"
    output=DOTArticle(states,output,final)
    output +="dummy -> 0"+"\n"
    output=connectLabels(states,labels,output)
    output +="}"
    return output+"\n"
}


func connectLabels(states [][]State,labels [][]string,output string)string{
    for i:=0;i<len(states);i++{
        for j:=0;j<len(labels[i]);j++ {
            if labels[i][j] != "" {
                output += strconv.Itoa(i) + " -> " + strconv.Itoa(j)+" [ label = \""+ labels[i][j][:len(labels[i][j])-2]+"\"]"
                output+="\n"
            }
        }
    }
    return output
}

func DOTArticle(states [][]State,output string,final []bool)string{
    for i:=0;i<len(states);i++{
        output +=strconv.Itoa(i)+" [ label =\"["
        for j:=0;j<len(states[i]);j++ {
            if j == len(states[i])-1 {
                output += strconv.Itoa(states[i][j].pos)
            } else {
                output += strconv.Itoa(states[i][j].pos) + " "
            }
        }
        output +="]\", shape = "
        if final[i]{
            output +="doublecircle]"
            output+="\n"
        }else{
            output +="circle]"+"\n"
        }
    }
    return output
}

func partrition(l,h int,z []State)int{
    i,j:=l,l
    for ;j<h;j++{
        if z[j].pos<z[h].pos{
            z[i],z[j]=z[j],z[i]
            i++
        }
    }
    z[i],z[h]=z[h],z[i]
    return i
}

func quickSort(z []State){
    quickSortRec(0, len(z)-1,z)
}
func quickSortRec(l,h int,z []State){
    if l<h{
        q:=partrition(l,h,z)
        quickSortRec(l,q-1,z)
        quickSortRec(q+1,h,z)
    }
}