Grafy problem z rozwiązaniem

Nie wiem jak mógłbym iść dalej oraz podać Graf nr 1/2, z podanych danych:

2
10 19
1 2 10
1 3 1
1 4 12
2 3 1
2 5 5
3 4 6
3 5 6
3 6 8
3 7 2
4 7 3
5 6 7
5 8 2
6 7 6
6 8 4
6 9 6
6 10 10
7 9 10
8 10 12
9 10 6
14 29
1 2 10
1 3 12
1 5 12
2 3 1
2 4 5
2 7 12
3 5 6
3 7 13
3 9 1
3 10 12
4 6 12
4 7 3
5 8 13
5 10 7
6 7 4
6 11 6
7 9 10
7 11 5
8 10 12
8 12 15
9 10 6
9 11 20
9 13 18
9 14 22
10 12 3
10 13 20
11 14 14
12 13 3
13 14 5

Wynik:

Graf nr 1
1-2 10
1-3 1
1-3-4 7
1-3-5 7
1-3-6 9
1-3-7 3
1-3-5-8 9
1-3-7-9 13
1-3-6-10 19

Graf nr 2
1-2 10
1-2-3 11
1-2-4 15
1-5 12
1-2-4-6 27
1-2-4-7 18
1-5-8 25
1-2-3-9 12
1-2-3-9-10 18
1-2-4-7-11 23
1-2-3-9-10-12 21
1-2-3-9-10-12-13 24
1-2-3-9-10-12-13-14 29

#include <iostream>

using namespace std;

const int MAXINT = 2147483647; // Największa liczba całkowita

// Typy danych
struct slistEl
{
    slistEl* next;
    int v, w;
};

// Zmienne globalne
int m, n;      // Liczba krawędzi i wierzchołków w grafie
slistEl** A;  // Tablica dynamiczna list sąsiedztwa
long long* d; // Tablica kosztów dojścia
int* p;       // Tablica poprzedników

// Funkcja wyznacza najkrótsze ścieżki
// v - wierzchołek startowy
// Wyjście:
// true  - wyniki w d i p
// false - graf zawiera ujemny cykl
//------------------------------------
bool BF(int v)
{
    int i, x;
    bool test;
    slistEl* pv;

    d[v] = 0;               // Zerujemy koszt dojścia do v
    for (i = 1; i < n; i++)   // Pętla relaksacji
    {
        test = true;             // Oznacza, że algorytm nie wprowadził zmian do d i p
        for (x = 0; x < n; x++) // Przechodzimy przez kolejne wierzchołki grafu
            for (pv = A[x]; pv; pv = pv->next) // Przeglądamy listę sąsiadów wierzchołka x
                if (d[pv->v] > d[x] + pv->w) // Sprawdzamy warunek relaksacji
                {
                    test = false;      // Jest zmiana w d i p
                    d[pv->v] = d[x] + pv->w; // Relaksujemy krawędź z x do jego sąsiada
                    p[pv->v] = x;   // Poprzednikiem sąsiada będzie x
                }
        if (test) return true;  // Jeśli nie było zmian, to kończymy
    }

    // Sprawdzamy istnienie ujemnego cyklu

    for (x = 0; x < n; x++)
        for (pv = A[x]; pv; pv = pv->next)
            if (d[pv->v] > d[x] + pv->w) return false; // ujemny cykl!!

    return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
int main()
{
    int i, v, x, y, w, sptr, * S;
    slistEl* rv, * pv;

    cin >> v >> n >> m;      // Wierzchołek startowy, liczba wierzchołków i krawędzi

    A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa
    d = new long long[n]; // Tworzymy tablicę kosztów dojścia
    p = new int[n];       // Tworzymy tablice poprzedników
    for (i = 0; i < n; i++) // Inicjujemy struktury danych
    {
        d[i] = MAXINT;
        p[i] = -1;
        A[i] = NULL;
    }

    for (i = 0; i < m; i++)
    {
        cin >> x >> y >> w; // Czytamy wierzchołki krawędzi oraz jej wagę
        pv = new slistEl;   // Tworzymy element listy
        pv->v = y;          // Inicjujemy go
        pv->w = w;
        pv->next = A[x]; // Dodajemy go na początek listy sąsiadów wierzchołka x
        A[x] = pv;
    }

    cout << endl;

    // Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

    if (BF(v))
    {
        S = new int[n];    // Tworzymy prosty stos
        sptr = 0;

        for (i = 0; i < n; i++)
        {
            cout << i << " - ";
            for (x = i; x != -1; x = p[x]) // Wierzchołki ścieżki umieszczamy na stosie
                S[sptr++] = x; // w kolejności od ostatniego do pierwszego

            while (sptr)       // Wierzchołki ze stosu drukujemy
                cout << S[--sptr] << " - "; // w kolejności od pierwszego do ostatniego

            cout << "$" << d[i] << endl; // Na końcu wyświetlamy koszt
        }
        delete[] S;         // Usuwamy stos
    }
    else cout << "Znaleziono cykl ujemny!" << endl;

    // Usuwamy struktury dynamiczne

    for (i = 0; i < n; i++)
    {
        pv = A[i];
        while (pv)
        {
            rv = pv;
            pv = pv->next;
            delete rv;
        }
    }

    delete[] A;
    delete[] d;
    delete[] p;

    return 0;
}

Losujesz dopóki nie trafisz?
Nie widzę żadnej sensownej reguły w tym "Graf nr 1/2" zwanym dalej "Graf 2" o ile o tym samym mowa.

co ten kod ma robić?

Może zacznij od uproszczenia struktury grafu, oraz uproszczenia wczytywania, oraz uproszczenia posługiwania się nim.

#include <iostream>
#include <iterator>
#include <vector>
#include <map>
using namespace std;

int main()
{
	istream_iterator<int> sin(cin);
	for(int test=*sin;test-->0;)
	{
		int size=*(++sin);
		vector<map<int,int>> graph(size+1); // graph[0] - not used
		for(int count=*(++sin);count-->0;)
		{
			int from=*(++sin),to=*(++sin),weight=*(++sin);
			graph[from][to]=weight;
		}
		cout<<"-------------"<<endl;
		for(int n=1;n<graph.size();++n)
		{
			for(auto p:graph[n]) cout<<n<<'\t'<<p.first<<'\t'<<p.second<<endl;
		}
	}	
    return 0;
}