public static void main(String[] args) throws Throwable {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (String line; (line=in.readLine())!= null;) {
			StringTokenizer st = new StringTokenizer(line);
			int m = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			if(m==0&&w==0) break;			
			n = m + (m-2);
			c = new int[n][n];
			t = m-1;
			mAdy = new int[n][n];
			for (int i = 0; i < m-2; i++) {
				st = new StringTokenizer(in.readLine());
				int k = Integer.parseInt(st.nextToken())-1;
				int v = Integer.parseInt(st.nextToken());
				c[ k ][ k + (m-1)] = v;
//				c[ k + (m-1) ][ k ] = v;
				
//								System.out.println( (k) +" "+ (k+(m-1))+" " + v);
			}

			for (int i = 0; i < w; i++) {
				st = new StringTokenizer(in.readLine());
				int k = Integer.parseInt(st.nextToken())-1;
				int l = Integer.parseInt(st.nextToken())-1;
				int v = Integer.parseInt(st.nextToken());
//								System.out.println("--------> " + k +" "+ l+" " + v);
				if( k != 0 && l != m-1 ){
					c[ k+(m-1) ][ l ] = v;
//										System.out.println( (k+(m-1)) +" "+ l+" " + v);
					c[ l+(m-1) ][ k ] = v;
//										System.out.println((l+(m-1)) +" "+ k+" " + v);
				}else if( k != 0 ){
					c[ k +(m-1) ][ l ] = v;
//										System.out.println((k+(m-1)) +" "+ l+" " + v);
//					c[ l ][  k +(m-1) ] = v;
//										System.out.println( l +" "+ (k+(m-1))+" " + v);
				}else if( l != m-1 ){
					c[ k ][ l ] = v;
//										System.out.println(k+" "+(l)+" "+v);
//					c[ l ][ k ] = v;
					//					System.out.println((l)+" "+k+" "+v);
				}else{
					c[ k ][ l ] = v;
				}
			}
//			imp(c);
		
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < n; j++) {
//					if( c[i][j] != 0 ){
////						mAdy[i][j]=1;
////						mAdy[j][i]=1;
//					}
//				}
//			}
//			imp(mAdy);
			
			
			sb.append(pushRelabel(c, s, t)+"\n");
		}
		System.out.print(new String(sb));
	}