Bellman-Ford nie działa dla specyficznych danych

Jako pracę muszę napisać algorytm Bellmana -Forda na tablicach. Program praktycznie działa dla większości danych, lecz są specyficzne dane w których program działa źle

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define inf 50000

using namespace std;

int main(void)
{
int      n,w, t; //liczba wierzcholkow
int      M[100][100];
int      d[100];

    cin >> t;
    while (t){
    cin >>n;
    for (int i = 0; i < n; i++) 
    for (int j = 0; j < n; j++) {
    cin >> M[i][j];
  

}


    for (int i = 1; i <=n; i++)
        d[i] = inf;
        d[0] = 0;
   
   
    for (int i = 1; i < n; i++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
               if (M[u][v] != 0) {
                if (d[u] + M[u][v] < d[v])
                d[v] = d[u] + M[u][v]; 
           
			}
		
		
			}
			
               
            }   
                for (int i = 0; i < n; i++)
                   
                printf("%d ", d[i]);
                printf ("\n"); 
            
                }
           
t--;
}


    return 0;

Oto kod, poniżej przedstawiam dane dla których program źle działa
1
8
0 0 0 0 0 0 0 0
0 0 53 70 0 0 0 64
0 0 0 0 34 0 0 0
0 -16 0 0 32 0 10 0
0 0 0 0 0 0 0 16
0 0 40 0 31 0 75 0
84 0 0 0 0 0 0 10
0 0 0 0 0 67 32 0

Pierwsza linia - liczba testów
Druga linia - liczba wierzchołków
Pozostałe linie - wagi
Wynikiem powinny być same zera (nieskączoność), a jak widzicie w jednej kolumnie pokazuje się liczba 4984.

Mam do ciebie taką prosbe, pisze projekt na zaliczenie i tam musze tez wykorzystac ten algorytm tylko dla duzo wiekszej tablicy, i moja prosba: czy mozesz dokladnie opisac caly tan kod... wszystkie zmienne itp, bede bardzo wdzieczny;)

w tym algorytmie podaje wartosc drogi od 1 wierzchołka do pozostałych, gdzie dokladnie jest pokazane ze to od tego wierzchołka? interesuje mnie mozliwosc ustawiania od ktoreg wierzcholka ma wyszukiwac droge