Bellman_Ford SSSP

//note that bellman ford still works for undirected graph bwt if the graph has a -ve edge than means it is a cycle
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace   std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

typedef long long LL;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef pair< LL, LL >PLL;
typedef pair< int, int > PII;

#define     sz                  size()
#define     pb                  push_back
#define     INF                 (1<<30)
#define     MOD                 (1000000007)
#define     PI                  (acos(-1.0));
#define     REP(i,n)            for(__typeof(n) i=0; i<(n); i++)
#define     FOR(i,a,b)          for(__typeof(b) i=(a); i<=(b); i++)
#define     ROF(i,a,b)          for(__typeof(b) i=(b); i>=(a); i--)
#define     FOREACH(it, l)      for(__typeof((l).begin()) it = (l).begin();  it != (l).end(); ++it)

//find_by_order(k) -> returns pointer to the k th order element, order_of_key(x) -> returns position of key x
typedef tree< int, null_type, less< int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
template<typename T> ostream& operator<<(ostream &os, const vector<T> &t) { LL n = t.size(); REP(i, n) os<<t[i]<<" "; return os; }
template<typename T,typename TT> ostream& operator<<(ostream &os, const pair<T,TT> &t) { return os<<"("<<t.first<<","<<t.second<<")"; }
/**__________________________________________________________________________________________________________________________________*/

#define M 10000
VI adj[M], cost[M];
int dis[M], pre[M];
int nodes, edges;


int bellmanFord(int source, int destination){
    FOR(i, 1, nodes)dis[i] = INF, pre[i] -1;
    dis[source] = 0;
    int cycle = -33;
    FOR(t, 1, nodes-1){
        bool update = false;
        FOR(u, 1, nodes){
            REP(i, adj[u].sz){
                int v = adj[u][i];
                if(dis[v] > dis[u] + cost[u][i]){
                    dis[v] = dis[u] + cost[u][i];
                    pre[v] = u;
                    update = true;
                }
            }
        }
        if(!update)break;
    }

    FOR(u, 1, nodes)REP(i, adj[u].sz){
        int v = adj[u][i];
        if(dis[v] > dis[u] + cost[u][i])return cycle;
    }

    return dis[destination];
}


int main(){
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //writes your codes here.........................


    cin>>nodes>>edges;
    FOR(i ,1, edges){
        int u, v, w;
        cin>>u>>v>>w;
        adj[u].pb(v), cost[u].pb(w);
        adj[v].pb(u), cost[v].pb(w);
    }

    int s, d;
    cin>>s>>d;

    int ans = bellmanFord(s, d);
    if(ans == -33){
        cout<<"Cycle Detected"<<endl;
        assert(ans != -33);
    }
    cout<<ans<<endl;

    FOR(i, 1, nodes)cout<<i<<"->"<<dis[i]<<endl;




    return 0;

}