책에 나와있는대로 벨만-포드와 플로이드 알고리즘 조합해서 풀어봤는데 계속 오답이 발생합니다.
algospot에서 관련 문제에 대한 testcase 찾아서 전부 돌려봐도 이상한 점은 못찾겠습니다.
출력 포맷도 확인해 봤지만 이것도 문제는 아닌 것 같습니다.
제가 놓치는 부분이 뭔지 알려주시면 고맙겠습니다.

~~~ c++

#include
#include
#include

using namespace std;

const int MAX_V = 100;
const int INF = 987654321;

int v;

vector > adj[MAX_V];

bool reachable[MAX_V][MAX_V];

int bellmanFord (int src, int target)
{
vector upper (v, INF);
upper[src] = 0;

for (int i = 0 ; i < v - 1 ; i++)
    for (int j = 0 ; j < v ; j++)
        for (int k = 0 ; k < adj[j].size() ; k++)
        {
            int t = adj[j][k].first;
            int w = adj[j][k].second;

            if (upper[t] > (upper[j] + w))
                upper[t] = upper[j] + w;
        }

for (int i = 0 ; i < v ; i++)
    for (int j = 0 ; j < adj[i].size() ; j++)
    {
        int t = adj[i][j].first;
        int w = adj[i][j].second;

        if (upper[t] > (upper[i] + w))
            if (reachable[src][i] && reachable[i][target])
                return -INF;
    }

return upper[target];

}

int main (int argc, char *argv[])
{
int test;

cin >> test;

while (test--)
{
    int w;
    int first, second;

    cin >> v >> w;

    for (int i = 0 ; i < MAX_V ; i++)
        adj[i].clear ();

    memset (reachable, false, sizeof (reachable));
    for (int i = 0 ; i < v ; i++)
        reachable[i][i] = true;

    for (int i = 0 ; i < w ; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back (make_pair (b, c));
        reachable[a][b] = true;
    }

    for (int i = 0 ; i < v ; i++)
        for (int j = 0 ; j < v ; j++)
            for (int k = 0 ; k < v ; k++)
                reachable[j][k] |= reachable[j][i] && reachable[i][k];

    first = bellmanFord (0, 1);

    if (first == INF)
    {
        cout << "UNREACHABLE" << endl;
        continue;
    }
    else if (first == -INF)
        cout << "INFINITY ";
    else
        cout << first << " ";

    for (int i = 0 ; i < v ; i++)
        for (int j = 0 ; j < adj[i].size() ; j++)
            adj[i][j].second = -adj[i][j].second;

    second = bellmanFord (0, 1);

    if (second == -INF)
        cout << "INFINITY" << endl;
    else
        cout << -second << endl;
}

return 0;

}
~~~