#include <iostream>
#include <utility>
#include <list>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

struct Edge;

struct Node
{
    Node(){}
    Node(unsigned int size):neighbours{size} {}

    int id;
    int capacity;

    vector<struct Edge*> neighbours;
};

struct Edge
{
    Edge(Node *n1, Node *n2, int capacity):n1{n1}, n2{n2}, capacity{capacity}, flow{0}
    {
        capacity = min(min(n1->capacity, n2->capacity), capacity);

        n1->neighbours.push_back(this);
        n2->neighbours.push_back(this);
    }

    Node *n1, *n2;
    int capacity;
    int flow;
};

int edmonds_karp(vector<Node> m)
{
    return 0;
}

int main()
{
    int num_machines, num_wires;

    while(cin >> num_machines >> num_wires)
    {
        if(!num_machines && !num_wires)
        {
            break;
        }

        vector<Node> machines(num_machines);
        machines[0].id = 1;
        machines[0].capacity = INT_MAX;
        machines[num_machines-1].id = num_machines;
        machines[num_machines-1].capacity = INT_MAX;

        for(int i = 0; i < num_machines-2; i++)
        {
            int id, capacity;
            cin >> id >> capacity;
            machines.at(id-1).id = id;
            machines.at(id-1).capacity = capacity;
        }

        for(int i = 0; i < num_wires; i++)
        {
            int node1, node2, capacity;
            cin >> node1 >> node2 >> capacity;
            node1--;
            node2--;

            Node *n1 = &machines[node1];
            Node *n2 = &machines[node2];

            new Edge(n1, n2, capacity);
        }


        cout << edmonds_karp(machines) << endl;

//        for(auto m : machines)
//        {
//            cout << m.id << ":" << m.capacity << endl;
//            for(auto n : m.neighbours)
//            {
//                cout << "\t" << n->n1->id << " <--> " << n->n2->id << ": " << n->capacity << endl;
//            }
//        }

    }

    return 0;
}