minimizing

import java.io.*;
import java.util.*;

public class AutomatoTask3 {

    class R {
        char c;
        int to;

        R(char c, int to) {
            this.c = c;
            this.to = to;
        }
    }

    class Automato {
        int n, m, k;
        ArrayList<R>[] hm;
        boolean[] end;

        Automato() {
            n = in.nextInt();
            m = in.nextInt();
            k = in.nextInt();
            hm = new ArrayList[n];
            end = new boolean[n];
            for (int i = 0; i < k; i++)
                end[in.nextInt() - 1] = true;
            for (int i = 0; i < n; i++)
                hm[i] = new ArrayList<>();
            for (int j = 0; j < m; j++) {
                int fr = in.nextInt() - 1;
                int to = in.nextInt() - 1;
                char c = in.next().charAt(0);
                hm[fr].add(new R(c, to));
            }
        }

        void print() {
            out.println(n + " " + m + " " + k);
            for (int i = 0; i < n; i++)
                if (end[i])
                    out.print((i + 1) + " ");
            out.println();
            for (int i = 0; i < n; i++)
                for (R entry : hm[i]) {
                    out.println((i + 1) + " " + (entry.to + 1) + " "
                            + entry.c);
                }
        }

        void removeInaccessibleStates() {
            int[] q = new int[n];
            int it = 0, sz = 1;
            boolean[] was = new boolean[n];
            was[0] = true;
            while (it < sz) {
                int v = q[it++];
                for (R entry : hm[v]) {
                    if (!was[entry.to]) {
                        q[sz++] = entry.to;
                        was[entry.to] = true;
                    }
                }
            }
            ArrayList<Integer>[] arrRev = new ArrayList[n];
            for (int i = 0; i < arrRev.length; i++)
                arrRev[i] = new ArrayList<>();
            for (int i = 0; i < n; i++)
                for (R entry : hm[i]) {
                    arrRev[entry.to].add(i);
                }
            boolean[] was2 = new boolean[n];
            for (int i = 0; i < n; i++)
                if (end[i] && !was2[i]) {
                    was2[i] = true;
                    it = 0;
                    sz = 1;
                    q[0] = i;
                    while (it < sz) {
                        int v = q[it++];
                        for (int j = 0; j < arrRev[v].size(); j++)
                            if (!was2[arrRev[v].get(j)]) {
                                was2[arrRev[v].get(j)] = true;
                                q[sz++] = arrRev[v].get(j);
                            }
                    }
                }
            int[] newId = new int[n];
            Arrays.fill(newId, -1);
            sz = 0;
            for (int i = 0; i < n; i++) {
                if (was[i] && was2[i])
                    newId[i] = sz++;
            }
            ArrayList<R>[] hm2 = new ArrayList[sz];
            for (int i = 0; i < hm2.length; i++)
                hm2[i] = new ArrayList<>();
            int m2 = 0;
            for (int i = 0; i < n; i++)
                if (was[i])
                    for (R entry : hm[i]) {
                        if (newId[entry.to] != -1) {
                            hm2[newId[i]].add(new R(entry.c,
                                    newId[entry.to]));
                            m2++;
                        }
                    }
            m = m2;
            hm = hm2;
            boolean[] end2 = new boolean[sz];
            for (int i = 0; i < n; i++)
                if (newId[i] != -1)
                    end2[newId[i]] = end[i];
            end = end2;
            n = sz;
            k = 0;
            for (int i = 0; i < n; i++)
                if (end[i])
                    k++;
        }
    }

    long edge(long from, long to, char c) {
        return (from << 40) + (to << 20) + c;
    }

    class MyLinkedList {
        Road first, last;
        int size;

        MyLinkedList() {
            first = new Road(-1, -1, 'a');
            last = new Road(-1, -1, 'a');
            first.next = last;
            last.prev = first;
            first.list = last.list = this;
        }

        void addElement(Road newRoad) {
            Road prevToLast = last.prev;
            prevToLast.next = newRoad;
            last.prev = newRoad;
            size++;
            newRoad.prev = prevToLast;
            newRoad.next = last;
        }

    }

    class Road {
        int from, to;
        char c;
        Road next, prev;
        MyLinkedList list;

        Road(int from, int to, char c) {
            this.from = from;
            this.to = to;
            this.c = c;
        }

        void removeThisElementFromList() {
            if (prev == null)
                return;
            prev.next = next;
            next.prev = prev;
            list.size--;
        }
    }

    Automato minimize(Automato a) {
        a.removeInaccessibleStates();
        if (a.n == 0) {
            return a;
        }
        n = a.n;
        int numberOfSets = 0;
        HashMap<Integer, Integer> toSetId = new HashMap<>();
        setId = new int[n];
        for (int i = 0; i < n; i++) {
            int hasRoads = a.end[i] ? 1 : 0;
            for (R entry : a.hm[i]) {
                hasRoads |= (1 << (entry.c - 'a' + 1));
            }
            Integer x = toSetId.get(hasRoads);
            if (x == null) {
                x = numberOfSets++;
                toSetId.put(hasRoads, x);
            }
            setId[i] = x;
        }
        roadsFrom = new ArrayList[n];
        roadsTo = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            roadsFrom[i] = new ArrayList<>();
            roadsTo[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++)
            for (R entry : a.hm[i]) {
                Road r = new Road(i, entry.to, entry.c);
                roadsFrom[i].add(r);
                roadsTo[r.to].add(r);
            }
        lists = new ArrayList<>();
        listsArr = new ArrayList<>();
        while (lists.size() < numberOfSets) {
            addNewSet();
        }
        maybeInterestingPairs = new HashSet<>();
        maybeInterestingPairsValsCharacter = new ArrayList<>();
        maybeInterestingPairsValsInteger = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < roadsFrom[i].size(); j++) {
                Road r = roadsFrom[i].get(j);
                addRoadToList(r);
            }
        int it = 0;
        while (it < maybeInterestingPairsValsCharacter.size()) {
            char c = maybeInterestingPairsValsCharacter.get(it);
            int id = maybeInterestingPairsValsInteger.get(it);
            if (!isPairInteresting(id, c)) {
                int val = (id << 5) + (c - 'a');
                maybeInterestingPairs.remove(val);
                it++;
            }
        }
        int x = setId[0];
        for (int i = 0; i < n; i++)
            if (setId[i] == 0) {
                setId[i] = x;
            } else {
                if (setId[i] == x) {
                    setId[i] = 0;
                }
            }
        int n2 = lists.size();
        boolean[] end = new boolean[n2];
        for (int i = 0; i < n; i++)
            end[setId[i]] = a.end[i];
        ArrayList<R>[] hm = new ArrayList[n2];
        for (int i = 0; i < n2; i++) {
            hm[i] = new ArrayList<>();
        }
        HashSet<Long> wasHS = new HashSet<Long>();
        for (int i = 0; i < n; i++)
            for (R entry : a.hm[i]) {
                long e = edge(setId[i], setId[entry.to], entry.c);
                if (wasHS.contains(e))
                    continue;
                wasHS.add(e);
                hm[setId[i]].add(new R(entry.c, setId[entry.to]));
            }
        a.m = 0;
        a.k = 0;
        for (int i = 0; i < n2; i++)
            a.m += hm[i].size();
        for (int i = 0; i < n2; i++)
            a.k += end[i] ? 1 : 0;
        a.end = end;
        a.hm = hm;
        a.n = n2;
        return a;
    }

    void addNewSet() {
        HashMap<Integer, MyLinkedList>[] tmp = new HashMap[26];
        ArrayList<PairIntegerLinkedList>[] tmp2 = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            // tmp[i] = new HashMap<>(0);
            // tmp2[i] = new ArrayList<>(0);
        }
        lists.add(tmp);
        listsArr.add(tmp2);
    }

    boolean isPairInteresting(int id, char c) {
        ArrayList<PairIntegerLinkedList> list = listsArr.get(id)[c - 'a'];
        for (int last = 0; last < 2; last++) {
            while (list.size() > last
                    && list.get(list.size() - last - 1).list.size == 0) {
                lists.get(id)[c - 'a']
                        .remove(list.get(list.size() - last - 1).val);
                list.remove(list.size() - last - 1);
            }
        }
        if (list.size() <= 1)
            return false;
        MyLinkedList l1 = list.get(list.size() - 1).list;
        MyLinkedList l2 = list.get(list.size() - 2).list;
        ArrayList<Integer> removedElements = new ArrayList<>();
        if (l1.size < l2.size) {
            Road r = l1.first.next;
            while (r != l1.last) {
                removedElements.add(r.from);
                r = r.next;
            }
        } else {
            Road r = l2.first.next;
            while (r != l2.last) {
                removedElements.add(r.from);
                r = r.next;
            }
        }
        addNewSet();
        for (int i = 0; i < removedElements.size(); i++) {
            int v = removedElements.get(i);
            setId[v] = lists.size() - 1;
        }
        for (int i = 0; i < removedElements.size(); i++) {
            int v = removedElements.get(i);
            for (int j = 0; j < roadsFrom[v].size(); j++) {
                roadsFrom[v].get(j).removeThisElementFromList();
                addRoadToList(roadsFrom[v].get(j));
            }
            for (int j = 0; j < roadsTo[v].size(); j++) {
                roadsTo[v].get(j).removeThisElementFromList();
                addRoadToList(roadsTo[v].get(j));
            }
        }
        return true;
    }

    HashSet<Integer> maybeInterestingPairs;
    ArrayList<Integer> maybeInterestingPairsValsInteger;
    ArrayList<Character> maybeInterestingPairsValsCharacter;

    void addMaybeInterestingPair(int from, char c) {
        int val = (from << 5) + (c - 'a');
        if (maybeInterestingPairs.contains(val))
            return;
        maybeInterestingPairs.add(val);
        maybeInterestingPairsValsCharacter.add(c);
        maybeInterestingPairsValsInteger.add(from);
    }

    void check(int id, char c) {
        if (lists.get(id)[c - 'a'] == null)
            lists.get(id)[c - 'a'] = new HashMap<Integer, AutomatoTask3.MyLinkedList>(
                    0);
        if (listsArr.get(id)[c - 'a'] == null)
            listsArr.get(id)[c - 'a'] = new ArrayList<>();
    }

    MyLinkedList getList(int setId, char c, int to) {
        check(setId, c);
        MyLinkedList result = lists.get(setId)[c - 'a'].get(to);
        if (result == null) {
            result = new MyLinkedList();
            lists.get(setId)[c - 'a'].put(to, result);
            PairIntegerLinkedList pair = new PairIntegerLinkedList(to, result);
            listsArr.get(setId)[c - 'a'].add(pair);
        }
        return result;
    }

    void addRoadToList(Road r) {
        MyLinkedList list = getList(setId[r.from], r.c, setId[r.to]);
        list.addElement(r);
        r.list = list;
        addMaybeInterestingPair(setId[r.from], r.c);
    }

    int n;
    int[] setId;
    ArrayList<Road>[] roadsFrom;
    ArrayList<Road>[] roadsTo;
    ArrayList<HashMap<Integer, MyLinkedList>[]> lists;
    ArrayList<ArrayList<PairIntegerLinkedList>[]> listsArr;

    class PairIntegerLinkedList {
        int val;
        MyLinkedList list;

        public PairIntegerLinkedList(int val, MyLinkedList list) {
            super();
            this.val = val;
            this.list = list;
        }

    }

    void solve() {
//      long st = System.currentTimeMillis();
        Automato a1 = new Automato();
        // Automato a2 = new Automato();
        // if (same(a1, a2)) {
        // out.println("YES");
        // } else {
        // out.println("NO");
        // }
        a1 = minimize(a1);
        a1.print();
//      System.err.println(System.currentTimeMillis() - st);
    }

    InputReader in;
    PrintWriter out;

    void runIO() {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    void run() {
        in = new InputReader(new File("fastminimization.in"));
        try {
            out = new PrintWriter(new File("fastminimization.out"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        solve();

        out.close();
    }

    public static void main(String[] args) {
        new AutomatoTask3().run();
    }

    class InputReader {
        BufferedReader bf;
        StringTokenizer st;

        InputReader(File f) {
            try {
                bf = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        InputReader(InputStream s) {
            bf = new BufferedReader(new InputStreamReader(s));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                String s;
                try {
                    s = bf.readLine();
                } catch (IOException e) {
                    return null;
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        boolean hasMoreElements() {
            while (!st.hasMoreElements()) {
                String s;
                try {
                    s = bf.readLine();
                } catch (IOException e) {
                    return false;
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }
    }
}