BellmanFord

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*BELLMANFORD*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
#include <bits/stdc++.h>

using namespace std;

const int MAX_NODE = 1000;
const int INF = 1e9;

vector <int> graph[ MAX_NODE ], cost[ MAX_NODE ];
int dist[ MAX_NODE ], node , edge ;
bool visit[ MAX_NODE ];

void ini()
{
     for( int i = 1 ; i <= node ; i++ )
    {
        visit[i] = 0;
        dist[ i ] = INF;
        graph[i].clear();
        cost[i].clear();
    }
}

void constructGraph()
{

    cin >> node >> edge;
    ini();
    int x , y, c;
    for( int i = 0 ; i < edge ; i++ )
    {
       cin >> x >> y >> c;
       graph[x].push_back(y);
       graph[y].push_back(x);
       cost[x].push_back(c);
       cost[y].push_back(c);
    }
}

void bellmanford(int source)
{
    dist[source] = 0;
    for( int i = 1 ; i < node ; i++ )
    {
        for( int j = 1 ; j <= node ; j++ )
        {
            int sz = graph[j].size();
            for( int k = 0 ; k < sz ; k++ )
            {
                int nxt = graph[j][k];
                if(dist[nxt] > dist[j] + cost[j][k] )
                {
                    dist[nxt] = dist[j] + cost[j][k];
                }
            }
        }
    }

    for( int j = 1 ; j <= node ; j++ )
        {
            int sz = graph[j].size();
            for( int k = 0 ; k < sz ; k++ )
            {
                int nxt = graph[j][k];
                if(dist[nxt] > dist[j] + cost[j][k] )
                {
                    printf("negative edge detected... ");
                    return ;
                }
            }
        }


    for( int i = 1; i <= node ; i++ )
    {
        printf("node :: %d dist :: %d\n",i , dist[i]);
    }
}

int main()
{
    constructGraph();
    bellmanford(1);

    return 0;
}