/*
 * Translation of bowen-dp-pokemon.cpp into java

  Dynamic programming with bitmask keeping track of
  - The current location.
  - Which pokemons have been caught.
  This has running time of O(L^2 * 2^M), where L is the number of locations,
  and M is the number of distinct pokemons.
*/
import java.util.*;

public class BowenDpPokemon {

    static class Pair implements Comparable<Pair> {
        public Pair() { first = second = 0; }
        public Pair(int a, int b) { first = a; second = b; }
        public int first, second;

        public boolean equals(Object other) {
            Pair p = (Pair)other;
            return first == p.first && second == p.second;
        }

        public int compareTo(Pair other) {
            if (first != other.first)
                return first - other.first;
            return second - other.second;
        }

        public int hashCode() { return (first << 16) | second; }
    }

    public static final int INF = (int)1E9;

    public static HashMap<String, Integer> pid = new HashMap<String, Integer>();
    public static HashMap<Pair, Integer> lid = new HashMap<Pair, Integer>();
    public static HashMap<Pair, Integer> pokemon = new HashMap<Pair, Integer>();
    public static HashMap<Integer, Integer> pokemask = new HashMap<Integer, Integer>();

    public static Pair loc[] = new Pair[21];
    public static int N, M, L, S, dp[][] = new int[21][1<<15];

    public static int dist(int i, int j) {
        return Math.abs(loc[i].first - loc[j].first) + Math.abs(loc[i].second - loc[j].second);
    }

    public static int solve(int x, int m) {
        if (m == (1<<M)-1) return dist(x, S);
        if (dp[x][m] != -1) return dp[x][m];
        int ans = INF;
        for (int y = 0; y < L; ++y) {
            int nm = m | pokemask.get(y);
            if (nm == m) continue;
            int s = solve(y, nm) + dist(x, y);
            if (s < ans)
                ans = s;
        }
        dp[x][m] = ans;
        return ans;
    }

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = L = 0;
        for (int i = 0; i < N; ++i) {
            Pair p = new Pair(in.nextInt(), in.nextInt());
            String s = in.next();
            if (!pid.containsKey(s))
                pid.put(s, M++);
            Integer x = pokemon.get(p);
            int y = (x == null) ? 0 : (int)x;
            pokemon.put(p, y | (1 << pid.get(s)));
        }

        if (!pokemon.containsKey(new Pair(0, 0))) {
            pokemon.put(new Pair(0,0), 0); // touch initial point
        }

        for (Map.Entry<Pair, Integer> it : pokemon.entrySet()) {
            lid.put(it.getKey(), L);
            loc[L] = it.getKey();
            pokemask.put(L, it.getValue());
            L++;
        }
        for (int arr[] : dp) { Arrays.fill(arr, -1); }
        S = lid.get(new Pair(0, 0));
        System.out.println(solve(S, pokemask.get(S)));
    }
}