package main

import "fmt"
import "strconv"
import "sort"

//================================================
//================================================
//================================================

//EdgeName .
type EdgeName struct {
    name   string
    number int
}

//-------------------------------------------------

//EdgeNames .
type EdgeNames []EdgeName

//-------------------------------------------------

func (edgeNames EdgeNames) Len() int {
    return len(edgeNames)
}

//-------------------------------------------------

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

//-------------------------------------------------

func (edgeNames EdgeNames) Swap(i, j int) {
    edgeNames[i], edgeNames[j] = edgeNames[j], edgeNames[i]
}

//================================================
//================================================
//================================================

//Node . Element of automaton
type Node struct {
    edges   []*Node
    input   []int
    signals []EdgeName
    isEnter bool
    name    int
}

//HyperNode . Node, contains other nodes.
type HyperNode struct {
    elements []*Node
    edges    []*HyperNode
    isEnter  bool
    name     int
    signals  map[*HyperNode][]string
}

//================================================
//================================================
//================================================

func (hyperNode *HyperNode) find(elem *Node) bool {
    for i := 0; i < len(hyperNode.elements); i++ {
        if elem.name == hyperNode.elements[i].name {
            return true
        }
    }
    return false
}

//-------------------------------------------------

func (hyperNode *HyperNode) add(elem *Node) {
    hyperNode.elements = append(hyperNode.elements, elem)
}

//-------------------------------------------------

func (hyperNode *HyperNode) getNameString() (name string) {

    var array []int
    array = make([]int, 0)

    for i := 0; i < len(hyperNode.elements); i++ {
        array = append(array, hyperNode.elements[i].name)
    }

    sort.Ints(array)

    for i := 0; i < len(array); i++ {

        if len(name) != 0 {
            name += " "
        }

        name += strconv.Itoa(array[i])
    }

    return name
}

//-------------------------------------------------

func (hyperNode *HyperNode) getEdgeString(b *HyperNode) (name string) {
    for _, value := range hyperNode.signals[b] {
        if len(name) != 0 {
            name += " "
        }
        name += value
    }
    return name
}

//-------------------------------------------------

func (hyperNode *HyperNode) contains(a []*HyperNode) bool {

    var count int

    for i := 0; i < len(a); i++ {

        count = 0

        if len(a[i].elements) != len(hyperNode.elements) {
            continue
        }

        for j := 0; j < len(a[i].elements); j++ {
            if a[i].elements[j].name == hyperNode.elements[j].name {
                count++
            }
        }
        if count == len(a[i].elements) {
            return true
        }
    }

    return false

}

//================================================
//==============MAIN FUNCTION====================
//================================================

func main() {
    nodes, startState, alphabet := getAutomaton()
    result := determinization(nodes, startState, alphabet)
    print(result, startState)
}

//================================================
//================================================
//================================================

func addToAlphabet(alphabet []string, element string) []string {
    for _, value := range alphabet {
        if value == element {
            return alphabet
        }
    }
    return append(alphabet, element)
}

func getAutomaton() (nodes []*Node, start int, alphabet []string) {
    var n, m int
    fmt.Scan(&n)
    fmt.Scan(&m)
    nodes = make([]*Node, n)
    alphabet = make([]string, 0)

    for i := 0; i < n; i++ {
        nodes[i] = new(Node)
        nodes[i].name = i
        nodes[i].edges = make([]*Node, 0)
        nodes[i].input = make([]int, 0)
        nodes[i].signals = make([]EdgeName, 0)
    }

    var in, out int
    var sygn string

    for i := 0; i < m; i++ {
        fmt.Scan(&in)
        fmt.Scan(&out)
        fmt.Scan(&sygn)
        nodes[in].edges = append(nodes[in].edges, nodes[out])
        nodes[out].input = append(nodes[out].input, in)
        alphabet = addToAlphabet(alphabet, sygn)
        nodes[in].signals = append(nodes[in].signals, EdgeName{sygn, i})
    }

    for i := 0; i < n; i++ {
        fmt.Scan(&in)
        if in == 1 {
            nodes[i].isEnter = true
        } else {
            nodes[i].isEnter = false
        }
    }

    fmt.Scan(&start)
    return nodes, start, alphabet
}

//================================================
//================================================
//================================================

func closure(set []*Node) (hyperNode *HyperNode) {
    hyperNode = new(HyperNode)
    hyperNode.elements = make([]*Node, 0)
    hyperNode.edges = make([]*HyperNode, 0)
    hyperNode.signals = make(map[*HyperNode][]string)

    for i := 0; i < len(set); i++ {
        dfs(set[i], hyperNode)
    }
    return hyperNode
}

//Helper for closure()
func dfs(elem *Node, hyperNode *HyperNode) {
    if !hyperNode.find(elem) {
        hyperNode.add(elem)
        for i := 0; i < len(elem.edges); i++ {
            if elem.signals[i].name == "lambda" {
                dfs(elem.edges[i], hyperNode)
            }
        }
    }
}

func makeSet(value string, hyperNode *HyperNode) (set []*Node) {
    set = make([]*Node, 0)
    for _, node := range hyperNode.elements {
        for k, edgeName := range node.signals {
            if edgeName.name == value {
                set = append(set, node.edges[k])
            }
        }
    }
    return set
}

//================================================
//================================================
//================================================

func determinization(nodes []*Node, startState int, alphabet []string) (result []*HyperNode) {
    count := 0

    var set []*Node
    set = make([]*Node, 0)
    set = append(set, nodes[startState])

    result = make([]*HyperNode, 0)
    startHyperNode := closure(set)

    var stack []*HyperNode
    stack = make([]*HyperNode, 0)
    stack = append(stack, startHyperNode)
    for len(stack) > 0 {
        hyper := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        for i := 0; i < len(hyper.elements); i++ {

            if hyper.elements[i].isEnter {
                hyper.isEnter = true
                break
            }
        }
        for _, value := range alphabet {

            set = makeSet(value, hyper)

            hyperNode := closure(set)

            if !hyperNode.contains(result) {
                hyperNode.name = count
                count++
                result = append(result, hyperNode)
                stack = append(stack, hyperNode)
            }

            _, ok := hyper.signals[hyperNode]
            if !ok {
                hyper.signals[hyperNode] = make([]string, 0)
            }
            if value != "lambda" {
                hyper.signals[hyperNode] = append(hyper.signals[hyperNode], value)
            }
        }
    }
    return result
}

//================================================
//================================================
//================================================

func print(result []*HyperNode, startState int) {
    fmt.Println("digraph {")
    fmt.Println("rankdir = LR")
    fmt.Println("dummy [label = \"\", shape = none]")

    for i := 0; i < len(result); i++ {
        fmt.Printf("%d [label = \"[%s]\", shape = ", i, result[i].getNameString())

        if result[i].isEnter {
            fmt.Println("doublecircle]")
        } else {
            fmt.Println("circle]")
        }
    }

    fmt.Println("dummy -> 0")

    for i, hyperNode := range result {
        for key := range hyperNode.signals {
            if len(hyperNode.signals[key]) != 0 {
                fmt.Printf("%d -> %d [label = %s]\n", i, key.name, hyperNode.getEdgeString(key))
            }
        }
    }

    // for i := 0; i < len(result); i++ {
    //  for
    //  // for j := 0; j < len(result[i].edges); j++ {
    //  //  fmt.Println("asdasdasdasd", result[i].edges[j].name)
    //  //  fmt.Printf("%d -> %d [label = %s]\n", i, result[i].edges[j].name, result[i].getEdgeString(result[result[i].edges[j].name]))
    //  // }
    // }
}