import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;
import java.util.PriorityQueue;

class Main {
  public static void main(String[] args) {
    In in = new In();
    Out out = new Out();
    out.SysInit(); 
    test(in, out);
  }
  
   public static void test(In in, Out out) {
        in.open("public/custom.in");
        out.compareTo("public/custom.out");
        int numTests = in.readInt();
        
        for (int t = 0; t < numTests; t++) {
            int n = in.readInt(); 
            int m = in.readInt(); 
            
            int[][] cost = new int[n+1][n+1];
            for (int i = 0; i < m; i++) {
                int u = in.readInt();
                int v = in.readInt();
                int c = in.readInt();
                cost[u][v] = c;
                cost[v][u] = c;
            }
            for (int i=0; i<n; i++) {
              cost[n][i] = cost[n-1][i];
              cost[i][n] = cost[n-1][i];
            }
            
            int[][] openHrs = new int[n+1][2];
            for (int i = 0; i < n-1; i++) {
                int open = in.readInt();
                int close = in.readInt();
                openHrs[i][0] = open;
                openHrs[i][1] = close;
            }
            openHrs[n-1][0] = openHrs[n][0] = 0;
            openHrs[n-1][1] = openHrs[n][1] = 24;
          int res = findPath(n-1, openHrs, cost);
          out.println(res);
        }
    }
    
    public static int findPath(int n, int[][] openHrs, int[][] cost) {
        ArrayList<ArrayList<ArrayList<Integer>>> E = new ArrayList<>();
        int hStart = n;
        int hEnd = n+1;
        
        // Step 1: Graph construction
        // ============================================================ 
        // create three copies for every vertex u
        for (int u=0; u<n; u++) {
          ArrayList<ArrayList<Integer>> layers = new ArrayList<>();
          layers.add(new ArrayList<>());
          layers.add(new ArrayList<>());
          layers.add(new ArrayList<>());
          E.add(layers); // add to adjacency list
        }
        
        // add one copy each for hStart and hEnd
        for (int i=0; i<2; i++) {
          ArrayList<ArrayList<Integer>> layer = new ArrayList<>();
          layer.add(new ArrayList<>());
          E.add(layer);
        }
        
        // connect hStart to first layer vertices if open in the morning
        // (we only need to keep track of vertex since layer is implied) 
        for (int v=0; v<n; v++) {
          if (openHrs[v][0] <= 9 && openHrs[v][1] >=12) E.get(hStart).get(0).add(v);
        }
        
        // connect morning-noon and noon-evening layers if opening hours are correct
        for (int lay=0; lay<2; lay++) {
          for (int u=0; u<n; u++) {
            for (int v=0; v<n; v++) {
              if (v==u) continue; // don't stay at same sight
              // exercise states that opening hours are contiguous blocks of multiples of 3
              if ( (openHrs[v][0] <= 12+(lay*3)) && (openHrs[v][1] >= 15+(lay*3)) ) {
                E.get(u).get(lay).add(v);
              }
        }}}
        
        // connect third layer to hEnd
        for (int i=0; i<n; i++) {
          E.get(i).get(2).add(hEnd);
        }
        
        // Step 2: Dijkstra
        // ============================================================
        // use pre-implemented Node class (see below, needs to implement Comparable interface in order to be compatible with Java's PriorityQueue)
        PriorityQueue<Node> Q = new PriorityQueue<>();
        int[][] dist = new int[n+2][4]; // note, 4 is used to facilitate distance computation between layers (see loop below)
        boolean[][] seen = new boolean[n+2][4]; // extra boolean array to check for stale entries (duplicates in PriorityQueue)
        for (int i = 0; i < n+2; i++) {
          Arrays.fill(dist[i], Integer.MAX_VALUE/2);
        }
        dist[hStart][0] = 0;
        
        for (int neigh: E.get(hStart).get(0)) {
          dist[neigh][0] = cost[hStart][neigh];
          Q.add(new Node(neigh, 0, dist[neigh][0])); // add first layer nodes to PriorityQueue
        }
        
        while(!Q.isEmpty()) {
          Node curr = Q.poll();
          if (curr.v == hEnd) break; // once hEnd is dequeued, final distance is computed -> break
          if (!seen[curr.v][curr.layer]) { // check for staleness
            seen[curr.v][curr.layer] = true;
            for (int neigh: E.get(curr.v).get(curr.layer)) {
              int c = cost[curr.v][neigh];
              int nextLay = curr.layer + 1;
              if (curr.dist + c < dist[neigh][nextLay]) {
                dist[neigh][nextLay] = curr.dist + c; // update distance
                Node newNode = new Node(neigh, nextLay, dist[neigh][nextLay]); // add neighbor to PriorityQueue
                Q.add(newNode);
              }
        }}}
        
        int res = dist[hEnd][3];
        return (res >= Integer.MAX_VALUE/2) ? -1 : res; // return distance to hEnd or -1 if unreachable
    }
    
    // PriorityQueue requires a comparable class
    // Since we want to keep track of multiple pieces of information (vertex, layer, distance)
    // but only order by distance, we need to implement a class of our own.
    static class Node implements Comparable<Node> {
      int v;
      int layer;
      int dist;
      
      public Node(int v, int layer, int dist) {
        this.v = v;
        this.layer = layer;
        this.dist = dist;
      }
       
      public int compareTo(Node other) {
        return this.dist-other.dist;
      }
    }
}