import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Solution to The Paladin
 * 
 * @author vanb
 */
public class paladin_vanb
{
    /** Input. */
    private static Scanner sc;
    
    /** Output. */
    private static PrintStream ps;
    
    private static final int MAX = 1000000;
    
    /**
     * Do it!
     */
    private void doit()
    {
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int k2 = k%2==0 ? k/2 : k/2+1;

        // costs[i][j] is the cost of letter pair (i+'a')(j+'a')
        int costs[][] = new int[26][26];
        
        // best[i][j] is the best you can do with a string of length j+1 ending in letter (i+'a')
        int best[][] = new int[26][k2];
        
        // Init the arrays
        for( int i=0; i<26; i++ )
        {
            Arrays.fill( costs[i], MAX );
            Arrays.fill( best[i], MAX );
            best[i][0] = 0;
        }
        
        // Read the letter pairs & costs
        for( int i=0; i<n; i++ )
        {
            String letters = sc.next();
            int a = letters.charAt( 0 )-'a';
            int b = letters.charAt( 1 )-'a';
            costs[a][b] = sc.nextInt();
        }
        
        // Go through the length of the desired string
        for( int i=1; i<k2; i++ )
        {
            // See what the best we can do at each point is...
            for( int a=0; a<26; a++ ) for( int b=0; b<26; b++ ) if( best[a][i-1]<MAX && costs[a][b]<MAX && costs[b][a]<MAX )
            {
                best[b][i] = Math.min( best[b][i], best[a][i-1] + costs[a][b] + costs[b][a] );
            }
        }
        
        // Special handling for even k
        if( k%2==0 )
        {
            // The palindrome has to look like abccba. Notice the double letters in the middle.
            for( int i=0; i<26; i++ ) if( best[i][k2-1]<MAX )
            {
                best[i][k2-1] = costs[i][i]==MAX ? MAX : best[i][k2-1]+costs[i][i];
            }
        }

        // Find the minimum at the full length, ending with any letter.
        int min = MAX;
        for( int i=0; i<26; i++ ) if( best[i][k2-1]<min ) min = best[i][k2-1];
        
        ps.println( min==MAX ? -1 : min );
    }
        
    /**
     * Main.
     * 
     * @param args unused
     * @throws Exception
     */
    public static void main( String[] args ) throws Exception
    {
        sc = new Scanner( System.in );
        ps = System.out;
        
        new paladin_vanb().doit();
    }

}