// Arup Guha
// 2/12/2017
// Solution to German Programming Contest Problem L: Maze

import java.util.*;

public class l {

	public static int n;
	public static ArrayList[] graph;

	public static void main(String[] args) {

		// Set up our graph.
		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		int e = stdin.nextInt();
		graph = new ArrayList[n];
		for (int i=0; i<n; i++)
			graph[i] = new ArrayList<edge>();
		int[][] freq = new int[n][26];

		// Read in each edge, keeping track of how many doors of each letter emanate from each vertex.
		for (int i=0; i<e; i++) {
			int v1 = stdin.nextInt()-1;
			int v2 = stdin.nextInt()-1;
			int let = stdin.next().charAt(0) - 'A';
			graph[v1].add(new edge(v2, let));
			graph[v2].add(new edge(v1, let));
			freq[v1][let]++;
			freq[v2][let]++;
		}

		// get directions.
		String dir = stdin.next();

		// Initial probabilities at time t = 0.
		double[] prob = new double[n];
		prob[0] = 1;

		// Go through each iteration.
		for (int i=0; i<dir.length(); i++) {

			// Will store probabilities for time t = i+1.
			double[] next = new double[n];

			// Go through all the locations except our end location.
			for (int j=0; j<n-1; j++) {

				// Find which door is open.
				int mylabel = dir.charAt(i)-'A';

				// See how many places I can go from j on this letter.
				int choices = freq[j][mylabel];

				// I am stuck in room j.
				if (choices == 0)
					next[j] += prob[j];

				// Will move definitely.
				else {

					// Only move to places with the correct door label and add in the appropriate probability.
					for (int k=0; k<graph[j].size(); k++) {
						edge cur = ((ArrayList<edge>)graph[j]).get(k);
						if (cur.label != mylabel) continue;
						next[cur.to] += prob[j]/choices;
					}
				}

			}

			// just stay at the goal destination.
			next[n-1] += prob[n-1];

			// update for next time step.
			prob = next;
		}

		// Ta da!
		System.out.println(prob[n-1]*100);
	}
}

class edge {

	public int to;
	public int label;

	public edge(int where, int letter) {
		to = where;
		label = letter;
	}
}