Dinic - Max Flow

#define FAST      ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ll        long long
#define inf       12345678

static const int MAXN = 100 + 5;

vector <int> graph[MAXN];
int tNode, tEdge;
ll cap[MAXN][MAXN];   // capacity of edge
ll flow[MAXN][MAXN];  // total sending flow
int level[MAXN];      // level of i'th node

int in(int x)
{
    return (x-1)*2;
}

int out(int x)
{
    return in(x) + 1;
}



bool bfs(int source, int sink)
{
    fill(begin(level), end(level), -1);
    queue <int> PQ;
    PQ.push(source);
    level[source] = 0;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        for (int &v : graph[u])
        {
            if (level[v] != -1 || flow[u][v] >= cap[u][v])
                continue;
            level[v] = level[u] + 1;
            PQ.push(v);
        }
    }
    return level[sink] != -1;
}
ll dfs(int u, ll minCap, int sink)
{
    if (u == sink)
        return minCap;
    for (int &v : graph[u])
    {
        if (level[v] == level[u] + 1 && flow[u][v] < cap[u][v])
        {
            ll minFlow = dfs(v, min(minCap, cap[u][v] - flow[u][v]), sink);
            if (minFlow > 0)
            {
                flow[u][v] += minFlow;
                flow[v][u] -= minFlow;
                return minFlow;
            }
        }
    }
    return 0;
}
ll DinicMaxFlow(int source, int sink)
{
    int maxFlow = 0;
    while (bfs(source, sink))
    {
        while (ll bottleneck = dfs(source, inf, sink))
        {
            maxFlow += bottleneck;
        }
    }
    return maxFlow;
}
void set_capacity(int u, int v, ll cost)
{
    cap[u][v] = cost;
    cap[v][u] = cost;
}
void add_edge(int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}
// for directed graph   -> cap[u][v] = c, flow[u][v] = 0
//                         cap[v][u] = 0, flow[v][u] = 0
// for undirected graph -> cap[u][v] = c, flow[u][v] = 0
//                         cap[v][u] = c, flow[v][u] = 0
int main()
{
    FAST;
    while (cin >> tNode >> tEdge)
    {
        if (tNode+tEdge == 0)
            break;
        int u = 1;
        int v = tNode;

        add_edge(in(u), out(u));
        set_capacity(in(u), out(u), inf);

        add_edge(in(v), out(v));
        set_capacity(in(v), out(v), inf);

        for (int e = 0; e < tNode-2; e++)
        {
            int i;
            ll c;
            cin >> i >> c; // node and its capacity
            add_edge(in(i), out(i));
            set_capacity(in(i), out(i), c);
        }
        for (int e = 0; e < tEdge; e++)
        {
            int j, k;
            ll d;
            cin >> j >> k >> d;  // edge and its capacity
            add_edge(out(j), in(k));
            cap[out(j)][in(k)] = d;
            add_edge(out(k), in(j));
            cap[out(k)][in(j)] = d;
        }
        int source = out(1);
        int sink = in(tNode);
        ll ans = DinicMaxFlow(source, sink);
        cout << ans << endl;
        memset(cap, 0, sizeof cap);
        memset(flow, 0, sizeof flow);
        for (int i = 0; i < MAXN; i++)
            graph[i].clear();
    }
}