snarknews [SNSS 2012, R3]. B

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>

template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }

using namespace std;

const int MAXN = 127;
const int INF = (int)1e+9;

int t;
int n, m, r;
int a[MAXN][MAXN];
int h[MAXN], l[MAXN];
int next[MAXN], prev[MAXN], upd[MAXN], cnt;
int block;

int dfs(int x)
{
    if (upd[x] == cnt) return 0;
    upd[x] = cnt;

    for (int i = 1; i <= n; i++)
        if (a[h[x]][i] == l[x] && i != block && prev[i] == 0)
        {
            next[prev[i] = x] = i;
            return 1;
        }

    for (int i = 1; i <= n; i++)
        if (a[h[x]][i] == l[x] && i != block && dfs(prev[i]))
        {
            next[prev[i] = x] = i;
            return 1;
        }

    return 0;
}


int main()
{
/*
        freopen("in", "r", stdin);
        freopen("out", "w", stdout);
*/
    memset(upd, 0, sizeof(upd));
    cnt = 0;

    cin >> t;
    while (t--)
    {
        cin >> m >> n >> r;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                a[i][j] = INF;
        for (int i = 1; i <= n; i++)
            a[i][i] = 0;
        memset(prev, 0, sizeof(prev));
        memset(next, 0, sizeof(next));

        for (int i = 1; i <= r; i++)
        {
            int x, y, l;
            cin >> x >> y >> l;
            a[x][y] = a[y][x] = min(a[x][y], l);
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
/*
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    printf("a[%d][%d] = %d\n", i, j, a[i][j]);
//*/

        for (int i = 1; i <= m; i++)
            cin >> h[i] >> l[i];

        int c = 0;
        block = 0;
        for (int i = 1; i <= m; i++)
        {
            cnt += 1;
            c += dfs(i);
//          if (c < i) break;
        }

        if (c < m)
        {
            puts("-1");
        }
        else
        {
            bool flag = true;
            for (int i = 1; i <= m && flag; i++)
            {
                block = next[i];
                cnt += 1;
                flag &= !dfs(i);
            }

            if (flag)
            {
                for (int i = 1; i <= m; i++)
                {
                    printf("%d", next[i]);
                    if (i < m) printf(" ");
                }
                printf("\n");
            }
            else
            {
                puts("-1");
            }
        }
    }

    return 0;
}