#include <iostream>

#include <string.h>

#include <algorithm>

#include <iostream>

using namespace std;

int max(int a,int b)

{return a<b?b:a;}

int min(int a,int b)

{return a<b?a:b;}

const int size = ;

const int INF = ;

bool map[size][size];         // 二分图的相等子图, map[i][j] = true 代表Xi与Yj有边

bool sx[size], sy[size]; // 标记在一次DFS中，Xi与Yi是否在交错树上

int match[size];             // 保存匹配信息，其中i为Y中的顶点标号，match[i]为X中顶点标号

bool DFS(int, const int);

void KM_Perfect_Match(const int n, const int edge[][size])

{

    int i, j;

    int lx[size], ly[size];   // KM算法中Xi与Yi的标号

    for(i = ; i < n; i++)

    {

        lx[i] = -INF;

        ly[i] = ;

        for(j = ; j < n; j++)

        {

            lx[i] = max(lx[i], edge[i][j]);

        }

    }

    bool perfect = false;

    while(!perfect)

    {

        // 初始化邻接矩阵

        for(i = ; i < n; i++)

        {

            for(j = ; j < n; j++)

            {

                if(lx[i]+ly[j] == edge[i][j])

                    map[i][j] = true;

                else map[i][j] = false;

            }

        }

        // 匹配过程

        int live = ;

        memset(match, -, sizeof(match));

        for(i = ; i < n; i++) {

            memset(sx, false, sizeof(sx));

            memset(sy, false, sizeof(sy));

            if(DFS(i, n)) live++;

            else {

                sx[i] = true;

                break;

            }

        }

        if(live == n) perfect = true;

        else {

            // 修改标号过程

            int ex = INF;

            for(i = ; i < n; i++)

            {

                for(j = ; sx[i] && j < n; j++)

                {

                    if(!sy[j])

                        ex = min(ex, lx[i]+ly[j]-edge[i][j]);

                }

            }

            for(i = ; i < n; i++)

            {

                if(sx[i]) lx[i] -= ex;

                if(sy[i]) ly[i] += ex;

            }

        }

    }

}

bool DFS(int p, const int n)//find augment path from X[p]

{

    int i;

    for(i = ; i < n; i++)

    {

        if(!sy[i] && map[p][i])

        {

            sy[i] = true;

            int t = match[i];

            match[i] = p;

            if(t == - || DFS(t, n))

            {

                return true;

            }

            match[i] = t;

            if(t != -) sx[t] = true;

        }

    }

    return false;

}

int main()

{

    int n, edge[size][size]; // edge[i][j]为连接Xi与Yj的边的权值

    int i;

    int m;

    /***************************************************

    *       record edge[i][j] as edge value between vertex i in X and vertex j in Y

    *       save n as vertexs need to be match (used in KM_Perfect_Match(n, edge);)

    ***************************************************/

    int s,d,pow;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n== && m==) break;

        memset(edge,,sizeof(edge));

        /*最小权: 去掉memset(edge,0,sizeof(edge));改为如下：

        for(i=0;i<n;i++)

            for(int j=0;j<n;j++)

                edge[i][j]=-INF;

        */

        memset(sx,,sizeof(sx));

        memset(sy,,sizeof(sy));

        memset(match,,sizeof());

        while(m--)

        {

            scanf("%d%d%d",&s,&d,&pow);

            s--;d--;

            /*最小权：edge[s][d]=pow; 改为edge[s][d]= - pow;*/

            edge[s][d]=pow;

        }

        KM_Perfect_Match(n, edge);

        int cost = ;

        for(i=;i<n;i++)

        {

            cost += edge[match[i]][i];

        }

        /*最小权：output 改为 -cost*/

        cout<<cost<<endl;

    }

    // cost 为最大匹配的总和, match[]中保存匹配信息

    return ;

}

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = ;

const int inf = 0x3f3f3f3f;

int N, L[maxn], Lx[maxn], Ly[maxn], W[maxn][maxn], slack[maxn];

bool S[maxn], T[maxn];

int match (int u) {

    S[u] = true;

    for (int i = ; i <= N; i++) if (!T[i]) {

        if (Lx[u] + Ly[i] == W[u][i]) {

            T[i] = true;

            if (!L[i] || match(L[i])) {

                L[i] = u;

                return true;

            }

        } else

            slack[i] = min(slack[i], Lx[u]+Ly[i]-W[u][i]);

    }

    return false;

}

void update () {

    int a = inf;

    for (int i = ; i <= N; i++) if (!T[i])

        a = min(a, slack[i]);

    for (int i = ; i <= N; i++) {

        if (S[i]) Lx[i] -= a;

        if (T[i]) Ly[i] += a;

    }

}

void KM () {

    for (int i = ; i <= N; i++) {

        L[i] = Lx[i] = Ly[i] = ;

        for (int j = ; j <= N; j++)

            Lx[i] = max(Lx[i], W[i][j]);

    }

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= N; j++) slack[j] = inf;

        while (true) {

            for (int j = ; j <= N; j++) S[j] = T[j] = false;

            if (match(i)) break;

            else update();

        }

    }

}

void init () {

    for (int i = ; i <= N; i++)

        for (int j = ; j <= N; j++)

            W[i][j] = -inf;

    int u, v;

    for (int i = ; i <= N; i++) {

        while (scanf("%d", &u) ==  && u) {

            scanf("%d", &v);

            W[i][u] = max(W[i][u], -v);

        }

    }

}

int main () {

    while (scanf("%d", &N) ==  && N) {

        init();

        KM();

        bool flag = false;

        for (int i = ; i <= N; i++) {

            if (L[i] && W[L[i]][i] == -inf)

                flag = true;

        }

        if (flag) printf("N\n");

        else {

            int ans = ;

            for (int i = ; i <= N; i++)

                ans += (Lx[i] + Ly[i]);

            printf("%d\n", -ans);

        }

    }

    return ;

}