import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author ilyakor
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    TaskF solver = new TaskF();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskF {

    public static final int GEN = 6;
    ArrayList<ii>[] g;
    int[] a;
    int res;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int n = in.nextInt();
      g = new ArrayList[n];
      for (int i = 0; i < n; ++i) {
        g[i] = new ArrayList<>();
      }
      for (int i = 0; i < n - 1; ++i) {
        int x = in.nextInt();
        int y = in.nextInt();
        int c = in.nextInt();
        g[x].add(new ii(y, c));
        g[y].add(new ii(x, c));
      }
      a = new int[16];
      res = 0;
      dfs(0, -1);
      int mask = 0;
      for (int i = 1; i < 16; ++i) {
        mask |= ((a[i] % 2) << i);
        res -= (a[i] % 2);
      }
      // best = 10000000;
      // //D = new HashMap<>();
      // go(a, 0);
      // res = best;

      Assert.assertTrue(res % 2 == 0);
      res /= 2;

      int[] d = new int[1 << 16];
      Arrays.fill(d, Integer.MAX_VALUE);
      d[mask] = 0;
      int[][] q = new int[GEN][(1 << 15) + 2];
      int[] ql = new int[GEN];
      q[0][ql[0]++] = mask;
      for (int dist = 0; dist < 30; ++dist) {
        int[] curQ = q[dist % GEN];
        int qr = 0;
        while (ql[dist % GEN] > qr) {
          int m = curQ[qr++];
          int val = d[m];
          for (int x = 1; x < 16; ++x) {
            for (int i = 1; i < 16; ++i) {
              if ((m >> i) % 2 == 1) {
                {
                  int nm = m ^ (1 << i);
                  int inc = 1;
                  int k = (i ^ x);
                  if ((nm >> k) % 2 == 1) {
                    ++inc;
                  }
                  if (k > 0) {
                    nm ^= (1 << k);
                  }
                  if (d[nm] > val + inc) {
                    d[nm] = val + inc;
                    q[(dist + inc) % GEN][ql[(dist + inc) % GEN]++] = nm;
                  }
                }
                for (int j = i + 1; j < 16; ++j) {
                  int inc = 1;
                  int nm = m ^ (1 << i) ^ (1 << j);
                  int ki = (i ^ x);
                  if ((nm >> ki) % 2 == 1) {
                    inc += 1;
                  }
                  if (ki > 0) {
                    nm ^= (1 << ki);
                  }
                  int kj = (j ^ x);
                  if ((nm >> kj) % 2 == 1) {
                    inc += 1;
                  }
                  if (kj > 0) {
                    nm ^= (1 << kj);
                  }
                  if (d[nm] > val + inc) {
                    d[nm] = val + inc;
                    q[(dist + inc) % GEN][ql[(dist + inc) % GEN]++] = nm;
                  }
                }
              }
            }
          }
        }
        ql[dist % GEN] = 0;
      }
      res += d[0];

      // ArrayList<DijkstraHeap.Edge>[] G = new ArrayList[1 << 16];
      // for (int i = 0; i < G.length; ++i)
      //     G[i] = new ArrayList<>();
      // for (int m = 1; m < (1 << 16); ++m) {
      //     for (int i = 0; i < 16; ++i) {
      //         {
      //             int nm = m ^ (1 << i);
      //             G[m].add(new DijkstraHeap.Edge(nm, 1));
      //         }
      //         for (int j = i + 1; j < 16; ++j) {
      //             int k = (i ^ j);
      //             int inc = 1;
      //             int nm = m ^ (1 << i) ^ (1 << j);
      //             if ((nm >> k) % 2 == 1) {
      //                 ++inc;
      //             }
      //             nm ^= (1 << k);
      //             G[m].add(new DijkstraHeap.Edge(nm, (long) inc));
      //         }
      //     }
      // }
      // long[] prio = new long[G.length];
      // int[] pred = new int[G.length];
      // DijkstraHeap.shortestPaths(G, mask, prio, pred);

      // int[] d = new int[1 << 16];
      // Arrays.fill(d, Integer.MAX_VALUE);
      // d[mask] = res;
      // int[][] q = new int[GEN][(1 << 15) + 2];
      // int[] ql = new int[GEN];
      // q[0][ql[0]++] = mask;
      // for (int dist = 0; dist < 100; ++dist) {
      //     int[] curQ = q[dist % GEN];
      //     int qr = 0;
      //     while (ql[dist % GEN] > qr) {
      //         int m = curQ[qr++];
      //         int val = d[m];
      //         for (int i = 1; i < 16; ++i) {
      //             {
      //                 int nm = m ^ (1 << i);
      //                 int inc = 2;
      //                 if ((m >> i) % 2 == 0 && a[i] >= 2) --inc;
      //                 if (d[nm] > val + inc) {
      //                     d[nm] = val + inc;
      //                     q[(dist + inc) % GEN][ql[(dist + inc) % GEN]++] = nm;
      //                 }
      //             }
      //             for (int j = i + 1; j < 16; ++j) {
      //                 int k = (i ^ j);
      //                 int inc = 2;
      //                 if ((m >> i) % 2 == 0 && a[i] >= 2) --inc;
      //                 if ((m >> j) % 2 == 0 && a[j] >= 2) --inc;
      //                 int nm = m ^ (1 << i) ^ (1 << j);
      //                 if ((nm >> k) % 2 == 1) {
      //                     inc += 2;
      //                 }
      //                 nm ^= (1 << k);
      //                 if (d[nm] > val + inc) {
      //                     d[nm] = val + inc;
      //                     q[(dist + inc) % GEN][ql[(dist + inc) % GEN]++] = nm;
      //                 }
      //             }
      //         }
      //     }
      //     ql[dist % GEN] = 0;
      // }
      // //res += d[0];
      // res = d[0];
      // Assert.assertTrue(res % 2 == 0);
      // res /= 2;

      // for (int nbits = 1; nbits <= 16; ++nbits) {
      //     for (int m = 1; m < (1 << 16); ++m)
      //         if (Integer.bitCount(m) == nbits) {
      //             d[m] = 1000000;
      //             for (int i = 0; i < 16; ++i)
      //                 if ((m >> i) % 2 == 1) {
      //                     {
      //                         int nm = m ^ (1 << i);
      //                         d[m] = Math.min(d[m], d[nm] + 1);
      //                     }
      //                     for (int j = i + 1; j < 16; ++j)
      //                         if ((m >> j) % 2 == 1) {
      //                             int k = (i ^ j);
      //                             int inc = 1;
      //                             int nm = m ^ (1 << i) ^ (1 << j);
      //                             if ((nm >> k) % 2 == 1) {
      //                                 ++inc;
      //                             }
      //                             nm ^= (1 << k);
      //                             d[m] = Math.min(d[m], d[nm] + inc);
      //                         }
      //                 }
      //         }
      // }
      // res += d[mask];
      //     // for (int m = 1; m < (1 << 16); ++m) if ((m & mask) == m && Integer.bitCount(m) == nbits) {
      //     //     int tot = 0;
      //     //     for (int i = 0; i < 16; ++i) if ((m >> i) % 2 == 1)
      //     //         tot ^= i;
      //     //     if (tot != 0) continue;
      //     //     mask ^= m;
      //     //     res += nbits - 1;
      //     // }
      // }

      //res += Integer.bitCount(mask);
      //res += (int) prio[0];
      out.printLine(res);
    }

    private int dfs(int x, int p) {
      int mask = 0;
      for (ii e : g[x]) {
        if (e.first != p) {
          int val = dfs(e.first, x);
          val ^= e.second;
          if (val != 0) {
            ++res;
          }
          ++a[val];
          //mask ^= val;
          mask ^= e.second;
        }
      }
      return mask;
    }

  }

  static class InputReader {

    private InputStream stream;
    private byte[] buffer = new byte[10000];
    private int cur;
    private int count;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public static boolean isSpace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public int read() {
      if (count == -1) {
        throw new InputMismatchException();
      }
      try {
        if (cur >= count) {
          cur = 0;
          count = stream.read(buffer);
          if (count <= 0) {
            return -1;
          }
        }
      } catch (IOException e) {
        throw new InputMismatchException();
      }
      return buffer[cur++];
    }

    public int readSkipSpace() {
      int c;
      do {
        c = read();
      } while (isSpace(c));
      return c;
    }

    public int nextInt() {
      int sgn = 1;
      int c = readSkipSpace();
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res = res * 10 + c - '0';
        c = read();
      } while (!isSpace(c));
      res *= sgn;
      return res;
    }

  }

  static class ii implements Comparable<ii> {

    public int first;
    public int second;

    public ii() {
    }

    public ii(int first, int second) {
      this.first = first;
      this.second = second;
    }

    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }

      ii ii = (ii) o;

      if (first != ii.first) {
        return false;
      }
      if (second != ii.second) {
        return false;
      }

      return true;
    }

    public int hashCode() {
      int result = first;
      result = 31 * result + second;
      return result;
    }

    public int compareTo(ii o) {
      if (first != o.first) {
        return first < o.first ? -1 : 1;
      }
      if (second != o.second) {
        return second < o.second ? -1 : 1;
      }
      return 0;
    }


    public String toString() {
      return "{" +
          "first=" + first +
          ", second=" + second +
          '}';
    }

  }

  static class Assert {

    public static void assertTrue(boolean flag) {
//        if (!flag)
//        while (true);
      if (!flag) {
        throw new AssertionError();
      }
    }

  }

  static class OutputWriter {

    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void printLine(Object... objects) {
      print(objects);
      writer.println();
    }

    public void close() {
      writer.close();
    }

  }
}



Measured memory_bytes: 75348